---
description: '# Medium'
---

# 114. Flatten Binary Tree to Linked List

{% hint style="info" %}
很有意思的一道题，思路其实不难，主要是recursive的思想，跟Tree没有太大关系。
{% endhint %}

### Solution:

1. transform `root.right` to `temp`.
2. flat `root.left` then transfer `root.right`.
3. assign `root` to `root2`, let `root2` goes to the bottom of the tree.
4. link `root2` with `flat(temp)`.
5. return `root`.
6. stop condition: `if root = NULL`, return imediately.

![Don't forget to return real root finally.](https://3288217904-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LxJcc9A1TOyn5a5HJQ4%2F-MB672Q6EJ2jD-DrkaMU%2F-MB6d9r4T5M670RNq96l%2F1593561075061.jpg?alt=media\&token=4dd2af33-e07e-4c66-9e4d-a2eb0847bd23)

{% tabs %}
{% tab title="C++" %}
```cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root) {  
        flat(root);        
    }
    
    TreeNode* flat(TreeNode *root) {
        // edge case
        if(root == NULL) return NULL;
        
        TreeNode *temp = root->right;
        
        root->right = flat(root->left);
        root->left = NULL;
        
        TreeNode *root2 = root;
        while(root2->right != NULL) {
            root2 = root2->right;
        }
        
        root2->right = flat(temp);
        
        return root;
    }
};
```
{% endtab %}

{% tab title="Second Tab" %}

{% endtab %}
{% endtabs %}

