114 Flatten Binary Tree to Linked List

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

Analysis:

link: https://leetcode.com/problems/flatten-binary-tree-to-linked-list/discuss/36987/Straightforward-Java-Solution

This solution is based on recursion. We simply flatten left and right subtree and paste each sublist to the right child of the root. (don’t forget to set left child to null)

Time Comlex: O(n^2)

Solution from Forum:

public void flatten(TreeNode root) {
    if(root==null)
        return;
    TreeNode left  = root.left;
    TreeNode right = root.right;
    flatten(root.left);
    flatten(root.right);
    root.left  = null;
    root.right = left; 
    while(root.right!=null) {
        root = root.right;
    }
    root.right = right;
}