# 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 };``````