Flatten Binary Tree to Linked List | Leetcode

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

click to show hints.

 

Hints: If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.

---

Solution: Use divide-and-conquer to handle the left and right child separately. For each node N, put the left subtree under the right child, set the left child to null, and put the right subtree under the last node of the tree consisting of N and the left subtree of N. This will give you the answer.

We are basically not using the hint of pre-order traversal in any way.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void flatten(TreeNode root) {
        flattenTree(root);
    }
    
    private TreeNode flattenTree(TreeNode node) {
        if (node == null) return null;
        
        // Flatten right and left tree separately.
        TreeNode right = flattenTree(node.right);
        TreeNode left = flattenTree(node.left);
        
        // Put left subtree under right child.
        node.right = left;
        
        // Left child will always be null.
        node.left = null;
        
        // Find last node of the left subtree including node.
        TreeNode temp = node;
        while (temp.right != null) temp = temp.right;
        
        // Append right subtree to the end of the left subtree.
        temp.right = right;
        
        return node;
    }
}