0114. Flatten Binary Tree to Linked List

# 114. Flatten Binary Tree to Linked List#

## 题目 #

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

## 解题思路 #

• 要求把二叉树“打平”，按照先根遍历的顺序，把树的结点都放在右结点中。

• 按照递归和非递归思路实现即可。

• 递归的思路可以这么想：倒序遍历一颗树，即是先遍历右孩子，然后遍历左孩子，最后再遍历根节点。

``````          1
/ \
2   5
/ \   \
3   4   6
-----------
pre = 5
cur = 4

1
/
2
/ \
3   4
\
5
\
6
-----------
pre = 4
cur = 3

1
/
2
/
3
\
4
\
5
\
6
-----------
cur = 2
pre = 3

1
/
2
\
3
\
4
\
5
\
6
-----------
cur = 1
pre = 2

1
\
2
\
3
\
4
\
5
\
6
``````
• 可以先仿造先根遍历的代码，写出这个倒序遍历的逻辑：

``````  public void flatten(TreeNode root) {
if (root == null)
return;
flatten(root.right);
flatten(root.left);
}
``````
• 实现了倒序遍历的逻辑以后，再进行结点之间的拼接：

``````  private TreeNode prev = null;

public void flatten(TreeNode root) {
if (root == null)
return;
flatten(root.right);
flatten(root.left);
root.right = prev;
root.left = null;
prev = root;
}
``````

## 代码 #

``````
package leetcode

/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/

// 解法一 非递归
func flatten(root *TreeNode) {
list, cur := []int{}, &TreeNode{}
preorder(root, &list)
cur = root
for i := 1; i < len(list); i++ {
cur.Left = nil
cur.Right = &TreeNode{Val: list[i], Left: nil, Right: nil}
cur = cur.Right
}
return
}

// 解法二 递归
func flatten1(root *TreeNode) {
if root == nil || (root.Left == nil && root.Right == nil) {
return
}
flatten(root.Left)
flatten(root.Right)
currRight := root.Right
root.Right = root.Left
root.Left = nil
for root.Right != nil {
root = root.Right
}
root.Right = currRight
}

// 解法三 递归
func flatten2(root *TreeNode) {
if root == nil {
return
}
flatten(root.Right)
if root.Left == nil {
return
}
flatten(root.Left)
p := root.Left
for p.Right != nil {
p = p.Right
}
p.Right = root.Right
root.Right = root.Left
root.Left = nil
}

``````

Apr 8, 2023