114. Flatten Binary Tree to Linked List.md

Solution1

class Solution {
    public void flatten(TreeNode root) {
        if (root == null)   return;
        TreeNode pre = null, cur = root;
        while (cur != null) {
            if (cur.left != null) {
                pre = cur.left;
                while (pre.right != null) {
                    pre = pre.right;
                }
                pre.right = cur.right;
                cur.right = cur.left;
                cur.left = null;
            }
            else {
                cur = cur.right;
            }
        }
    }
}

note

• time O(N+E) space O(1)
• Iterative approach. The idea is to use a pre node to flatten current node's left subtree to current node's right and attach its original right subtree to this inserted subtree. Move current node to its right and repeat until current node is null which means we have flattend the whole tree.
• Don't forget to set cur's left to null each time we flattened left tree to right.