# 114. Flatten Binary Tree to Linked List 二叉树展开为链表

@TOC

## # 题目描述

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
``````

## # 解题方法

### # 先序遍历

python代码如下：

``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def flatten(self, root):
"""
:type root: TreeNode
:rtype: void Do not return anything, modify root in-place instead.
"""
res = []
self.preOrder(root, res)
for i in range(len(res) - 1):
res[i].left = None
res[i].right = res[i + 1]

def preOrder(self, root, res):
if not root: return
res.append(root)
self.preOrder(root.left, res)
self.preOrder(root.right, res)
``````

### # 递归

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

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

2是root,3是left,4是right。修改成下面这样：

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

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

python代码：

``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def flatten(self, root):
"""
:type root: TreeNode
:rtype: void Do not return anything, modify root in-place instead.
"""
if not root: return
left = root.left
right = root.right
root.left = None
self.flatten(left)
self.flatten(right)
root.right = left
cur = root
while root.right:
root = root.right
root.right = right
``````

C++代码：

``````/**
* 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) {
if (!root) return;
TreeNode* left = root->left;
TreeNode* right = root->right;
root->left = nullptr;
flatten(left);
flatten(right);
root->right = left;
TreeNode* cur = root;
while (cur->right)
cur = cur->right;
cur->right = right;
}
};
``````

Java代码：

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public void flatten(TreeNode root) {
if(root == null){
return;
}
TreeNode left = root.left;
TreeNode right = root.right;
root.left = null;
flatten(left);
flatten(right);
root.right = left;
TreeNode cur = root;
while(cur.right != null){
cur = cur.right;
}
cur.right = right;
}
}
``````

## # 日期

2017 年 4 月 19 日 2019 年 1 月 7 日 —— 新的一周开始啦啦啊