114 Flatten Binary Tree to Linked List

114. Flatten Binary Tree to Linked List

1. Question

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

2. Implementation

(1) Morris Tree Traversal

class Solution {
    public void flatten(TreeNode root) {
        TreeNode curNode = root, preNode = root;

        while (curNode != null) {
            if (curNode.left == null) {
                curNode = curNode.right;
            }
            else {
                preNode = curNode.left;
                while (preNode.right != null) {
                    preNode = preNode.right;
                }
                preNode.right = curNode.right;
                curNode.right = curNode.left;
                curNode.left = null;
                curNode = curNode.right;
            }
        }
    }
}

(2) DFS recursion

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

        TreeNode rightSubTree = root.right;
        root.right = root.left;
        root.left = null;

        TreeNode curNode = root;
        while (curNode.right != null) {
            curNode = curNode.right;
        }
        curNode.right = rightSubTree;

        flatten(root.right);
    }

(3) DFS iteration

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

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

        while (!stack.isEmpty()) {
            TreeNode curNode = stack.pop();

            if (curNode.right != null) {
                stack.push(curNode.right);
            }

            if (curNode.left != null) {
                stack.push(curNode.left);
            }

            if (!stack.isEmpty()) {
                curNode.right = stack.peek();
            }
            curNode.left = null;
        }
    }
}

3. Time & Space Complexity

Morris Tree Traversal: 时间复杂度O(n), 空间复杂度O(1)

DFS recursion: 时间复杂度O(n), 空间复杂度O(n)

DFS iteration: 时间复杂度O(n), 空间复杂度(n)