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
C++:
01 /**
02  * Definition for binary tree
03  * struct TreeNode {
04  *     int val;
05  *     TreeNode *left;
06  *     TreeNode *right;
07  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
08  * };
09  */
10  void flattenHelper(TreeNode* root, TreeNode*& prv)
11  {
12      if(root==NULL)
13         return;
14      TreeNode* left=root->left;
15      TreeNode* right=root->right;
16      if(prv!=NULL)
17         prv->right=root;
18      root->left=NULL;
19      prv=root;
20      flattenHelper(left,prv);
21      flattenHelper(right,prv);
22  }
23 class Solution {
24 public:
25     void flatten(TreeNode *root) {
26         // Start typing your C/C++ solution below
27         // DO NOT write int main() function
28         TreeNode* prv=NULL;
29         flattenHelper(root,prv);
30     }
31 };
Advertisements
This entry was posted in Array and linked list, Tree. 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