Problem

Flatten a binary tree to a fake "linked list" in pre-order traversal.

Here we use the right pointer in TreeNode as the next pointer in ListNode.

 Notice

Don't forget to mark the left child of each node to null. Or you will get Time Limit Exceeded or Memory Limit Exceeded.

Example
              1
               \
     1          2
    / \          \
   2   5    =>    3
  / \   \          \
 3   4   6          4
                     \
                      5
                       \
                        6

思路一（divide & conquer）

1. 假设左子树和右子树已经转换好了, 变成l1 和 l2, 考虑如何连接根节点
2. 如果 l1 是空的话,
   1. root.right只需要连接l2, root.left = null
3. 如果 l2 是空的话,
   1. root.right连接l1, root.left = null
4. 如果都不为空
   1. 左子树最后一个节点连接右子树, root.right连接左子树, root.left = null

    public void flatten(TreeNode root) {
        root = flattenToList(root);
    }

    private TreeNode flattenToList(TreeNode root) {
        if (root == null) {
            return null;
        }
        if (root.left == null && root.right == null) {
            return root;
        }

        TreeNode left = flattenToList(root.left);
        TreeNode right = flattenToList(root.right);

        if (left != null && right != null) {
            left.right = root.right;
            root.right = root.left;
            root.left = null;
            return right;
        }

        if (left != null) {
            left.right = null;
            root.right = root.left;
            root.left = null;
            return left;
        }

        if (right != null) {
            root.left = null;
            return right;
        }

        return null;
    }

思路二 (inorder traversal)

// version 1, using instance/method variable
object Solution {
    def flatten(root: TreeNode): Unit = {
        var lastNode: TreeNode = null
        def helper(root: TreeNode): Unit  = {
            if (root == null) return
            if (lastNode != null) {
                lastNode.left = null
                lastNode.right = root
            }
            lastNode = root
            val leftNode = root.left
            val rightNode = root.right
            helper(leftNode)
            helper(rightNode)
        }
        helper(root)
    }
}
// version 2, using method input parameter and return value
    def flatten(root: TreeNode): Unit = {
        def helper(root: TreeNode, lastNode: TreeNode): TreeNode = {
            if (root == null) return lastNode
            if (lastNode != null) {
                lastNode.left = null
                lastNode.right = root
            }
            val rightNode = root.right
            val leftLast = helper(root.left, root)
            val rightLast = helper(rightNode, leftLast)
            rightLast
        }

        helper(root, null)
    }

思路三(stack)

    def flatten(root: TreeNode): Unit = {
        if (root == null) return
        import scala.collection.mutable.{Stack, ArrayBuffer}
        val stack = Stack[TreeNode](root)
        val res = ArrayBuffer[TreeNode]()
        while (stack.nonEmpty) {
            val node = stack.pop
            res.append(node)
            if (node.right != null) {
                stack.push(node.right)
            }
            if (node.left != null) {
                stack.push(node.left)
            }
        }
        (0 until res.size - 1).foreach { idx =>
            res(idx).left = null
            res(idx).right = res(idx + 1)
        }
    }