flatten binary tree to linked list

flatten binary tree to linked list

Recursive

For each node, flat its left child and flat its right child. If left child exsits, put it to right, and connect right child. Otherwise, keep the right stay on site.When change the left, set NULL!

 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     void flatten(TreeNode *root) {
13         root = build(root);
14     }
15     TreeNode* build( TreeNode* root ) {
16         if ( !root ) {
17             return NULL;
18         }
19         TreeNode* left = build(root->left);
20         TreeNode* right = build(root->right);
21         if ( left ) {
22             root->right = left;
23             TreeNode* p = root->right;
24             while( p->right ) {
25                 p = p->right;
26             }
27             p->right = right;
28         } else {
29             root->right = right;
30         }
31         root->left = NULL;
32         return root;
33     }
34 };

Loading Disqus comments...
Table of Contents