Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

Screen Shot 2016-04-11 at 8.40.15 PM

The flattened tree should look like:

Screen Shot 2016-04-11 at 8.40.22 PM


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

        TreeNode realRight = root.right;
        if (lastvisited != null) {
            lastvisited.left = null;
            lastvisited.right = root;
        }
        //both lastvisited and root are reference
        //Thus, changing lastvisited is equivalent to changing root!!
        lastvisited = root;
        flatten(root.left);
        flatten(realRight);
    }
}
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