Leetcode–Flatten Binary Tree to Linked List

The Problem:

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

Notes:

  1. Use a stack to record node.right if need to move node.left there.
  2. Mistake I made : remember to reset the node.left to null if moved.

Java Solution

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void flatten(TreeNode root) {
        if(root == null) return ;
        Stack<TreeNode> st = new Stack<TreeNode>();
        st.push(root);
        TreeNode fkHead = new TreeNode(0);
        TreeNode pre = fkHead;
        while(!st.empty()){
            TreeNode p = st.pop();
            pre.right = p;
            pre = p;
            while(p.right!= null || p.left != null){
                if(p.right!= null && p.left != null){
                    //--!!--only push to stack if both not null
                    st.push(p.right);
                    p.right = p.left;
                    //--!!!---remember to remove the left from tree
                    p.left = null;
                }
                else if(p.left != null){
                    p.right = p.left;
                    //--!!!---remember to remove the left from tree
                    p.left = null;
                }
                p = p.right;
                pre = p;
            }
        }
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s