114. Flatten Binary Tree to Linked List Leetcode Java

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:

As we can see from the example given in the question, the flatten process is basically 2 cases:
1. root node doesn't have left child, which is easy, root=root.right, continue, 
2. root node does have left child, then find the rightmost node of left child, and insert the whole path between the root node and root.right node. by a) setting root.right=root.left; b) setting rightmost.right=original root.right; c) setting root.left=null. 
Do this process iteratively until the root is null.
Since each node and each edge will be visited at most twice, the time complexity: O(n)

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