题解：
思路一：
迭代, 可以发现展开的顺序其实就是二叉树前序遍历。
- 将左子树插入到右子树
- 将原来的右子树插入到左子树最右边节点
- 考虑新的右子树的根节点，重复上边的过程
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
|
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
23
24
25
26
27
28
29
30
31
32
33
|
// 第一步：将左子树 插入到右子树上
// 第二步：将之前的右子树 插入到之前左子树的最右边节点
// 第三部：考虑新的右子树的根节点，重复上边的过程
public void flattern(TreeNode root){
while (root != null){
if (root.left == null){
// 如果没有左子树，直接处理其右子树
root = root.right;
continue;
}
// 将原来右子树保存一份
TreeNode tmp = root.right;
// 把左子树 插入 到右子树的位置
root.right = root.left;
// 清空原来左子树
root.left = null;
// 找到原来 左子树的最右边节点
TreeNode pre = root.right;
while (pre.right != null){
pre = pre.right;
}
// 原来的右子树 插入到 原来左子树的最右边
pre.right = tmp;
root = root.right;
}
}
|
思路二：
递归： 其实跟上述做法思路类似
- 分别将左子树 和 右子树变为链表
- 把左子树插入到右子树的位置，
- 将原来右子树插入到原来左子树的最右边
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
|
// 递归
// 第一步 左子树变为链表
// 第二步 右子树变为链表
// 第三步 原来的左子树 插入到右子树的位置
// 第四步 清空原来的左子树
// 第五步 把原来的右子树 插入到原来左子树的最右边
public void flatten(TreeNode root){
if (root == null) return;
// 左子树变为链表
flatten(root.left);
// 右子树变为链表
flatten(root.right);
// 保存原来的右子树
TreeNode tmp = root.right;
// 左子树插入到右子树位置
root.right = root.left;
// 清空左子树
root.left = null;
// 找到左子树的最右边
TreeNode pre = root.right;
while (pre.right != null){
pre = pre.right;
}
// 原来的右子树 插入到左子树的最右边
pre.right = tmp;
}
|