> For the complete documentation index, see [llms.txt](https://kongchengzhuge.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kongchengzhuge.gitbook.io/leetcode/114.-flatten-binary-tree-to-linked-list.md).

# 114. Flatten Binary Tree to Linked List

## problem description

Given a binary tree, flatten it to a linked list in-place.

For example, given the following tree:

```
    1
   / \
  2   5
 / \   \
3   4   6
```

The flattened tree should look like:

```
1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6
```

## algorithm thought

观察知道，最后所有节点全部在右边展平，我们可以每次将左子树插入到右子树，原来的右子树接在左子树最后面，重复这个操作，直到所有的右子树都展平即可

## code

```cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root) {
        while(root){
            if(root->left){
                TreeNode* ma=findmax(root->left);
                ma->right=root->right;
                root->right=root->left;
                root->left=NULL;
            }
            root=root->right;
        }
    }
    TreeNode* findmax(TreeNode* root){
        if(root)
        while(root->right){
            root=root->right;
        }
        return root;
    }
};
```

## algorithm analysis

时间复杂度O(n),对于所有节点，最多访问节点两次，访问总次数是2n，所以最后时间复杂度O(n)