给定一个二叉树，原地将它展开为链表。

77 阅读 0 评论 51 点赞

我是靠谱客的博主粗犷红牛，这篇文章主要介绍给定一个二叉树，原地将它展开为链表。，现在分享给大家，希望可以做个参考。

给定一个二叉树，原地将它展开为链表。

例如，给定二叉树

复制代码

1
2
1

/
2 5
/
3 4 6
将其展开为：

1

2

3

4

5

6

思路：可以发现展开的顺序其实就是二叉树的先序遍历。算法和 94 题中序遍历的 Morris 算法有些神似，我们需要两步完成这道题。
将左子树插入到右子树的地方
将原来的右子树接到左子树的最右边节点
考虑新的右子树的根节点，一直重复上边的过程，直到新的右子树为 null

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
可以看图理解下这个过程。
Java
1
/ 
2
5
/ 

3
4
6
//将 1 的左子树插入到右子树的地方
1

2
5
/ 

3
4
6
//将原来的右子树接到左子树的最右边节点
1

2
/ 
3
4

5

6
//将 2 的左子树插入到右子树的地方
1

2

3
4

5

6
//将原来的右子树接到左子树的最右边节点
1

2

3

4

5

6

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public void flatten(TreeNode root) {
while (root != null) {
//左子树为 null，直接考虑下一个节点
if (root.left == null) {
root = root.right;
} else {
// 找左子树最右边的节点
TreeNode pre = root.left;
while (pre.right != null) {
pre = pre.right;
}
//将原来的右子树接到左子树的最右边节点
pre.right = root.right;
// 将左子树插入到右子树的地方
root.right = root.left;
root.left = null;
// 考虑下一个节点
root = root.right;
}
}
}