114. Flatten Binary Tree to Linked List (Meidum)

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

Solution 1: Iterative O(n); O(1) 直观

很透彻 Time is O(n), here’s why: You’re moving now over all nodes and for each one potentially dive down deep into its left subtree, so one might think it’s more than O(n) time. But… a long path down the left subtree immediately pays off, as you then insert that entire path into the “right border” of the whole tree, where now will walk over it once more but pre will never have to walk over it again.

To put it differently: Every node is visited by now exactly once and by pre at most once, and the runtime is proportional to the number of steps taken by now and pre, so O(n) overall.

    /**
     * Iterative O(n); O(1)
     * For current node:
     *   If left subtree is not null:
     *     Find the right most node of left subtree.
     *     Connect it with cur.right.
     *     Set cur.right to cur.left.
     *   Move cur to cur.right, which was cur.left.
     * Repeat until root is null.
     */
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }

        TreeNode cur = root;
        while (cur != null) {
            if (cur.left != null) {
                TreeNode rightMost = cur.left;
                while (rightMost.right != null) {
                    rightMost = rightMost.right;
                }
                rightMost.right = cur.right; //cur.right can be null
                cur.right = cur.left; //题目要求，左空右直
                cur.left = null; //题目要求，左空右直
            }
            cur = cur.right;
        }
    }

Solution 2: Recursive, ‘reversed’ preorder O(n); O(h)

    private TreeNode prev = null;

    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }

        flatten(root.right);
        flatten(root.left);
        root.right = prev;
        root.left = null;
        prev = root;
    }

Solution 3: Iterative + Stack O(n); O(h)

    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.empty()) {
            TreeNode node = stack.pop();
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }

            // connect 
            node.left = null;
            if (stack.empty()) {
                node.right = null;
            } else {
                node.right = stack.peek();
            }
        }
    }