Flatten Binary Tree

LeetCodeLink
I have solved this problem weeks ago, but today I completely forgot how I had solved it. As I tried to simulate the interview, I started to think and finally came up with a solution, which is interestingly different from the previous one. That’s what I want to write about this problem, not because it’s difficult or intriguing itself, but because it encouraged me to think twice from different perspective.

My first solution idea is that the problem can be solved by tweaking DFS: inorder traversal. We just need to keep track of the current pointer and the next one.

    void dfs(TreeNode* root, TreeNode* next){
        if(!root){
            return;
        }
        if(!root->left && !root->right){
            root->right = next;
            return;
        }
        else if(root->left){
            if(root->right){
                dfs(root->left, root->right);
                dfs(root->right, next);
            }
            else{
                dfs(root->left, next);
            }
            root->right = root->left;
            root->left=NULL;
        }
        else{
            dfs(root->right,next);
        }
    }

The other solution I came up today involve return the result as a pair of pointer.

    Pair flatten(TreeNode* root){
        if(!root){
            return Pair(NULL,NULL);
        }
        if(!root->left && !root->right){
            return Pair(root,root);
        }
        else if(root->left){
            Pair left=flatten(root->left);
            Pair right=flatten(root->right);
            root->left=NULL;
            root->right=left.first;
            left.second->right=right.first;
            if(right.second)
                return Pair(root,right.second);
            else
                return Pair(root,left.second);
        }
        else{
            Pair right = flatten(root->right);
            return Pair(root,right.second);
        }
    }

The two solutions are essential the same, but the point of practicing this problem is thinking path, not memorizing. There are tons of interesting problems come from binary tree, the more I solve, the more intuitive my thinking is.

Advertisements
This entry was posted in Computer Science, LeetCode. Bookmark the permalink.

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