114. 二叉树展开为链表

描述

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

例如,给定二叉树

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

将其展开为:

1
2
3
4
5
6
7
8
9
10
11
1
\
2
\
3
\
4
\
5
\
6

来源:力扣(LeetCode)
链接:114. Flatten Binary Tree to Linked List

解题思路

这题要求把二叉树展开成链表,根据展开后形成的链表的顺序分析,可以看出使用的是先(前)序遍历,即根节点->左孩子节点->右孩子节点。但凡是树的遍历,必然就有递归和非递归版本。首先来看迭代的版本。

思路和94. 二叉树的中序遍历中序遍历的Morris算法有些神似,我们需要三步完成这道题。

  • 将原来的右子树接到左子树的最右边节点
  • 将左子树插入到右子树的地方
  • 考虑右子树的节点是否有左子树,如果有则重复上述过程,直到遍历到右子树的尽头

上述过程图示如下:

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

代码写起来还是比较容易的,具体见解法一,里面有详细的注释。

下面来看看递归的解法,对于树的问题,如果没有用上递归,就仿佛不完整。

递归的主要思路是利用DFS的思路找到最左子节点,然后回到其父节点,把其父节点和右子节点断开,将原左子节点连上父节点的右子节点,然后再把原右子节点连到新右子节点的右子节点上,再回到上一父节点做相同的操作。

上述过程图示如下:

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
57
58
59
60
61
62
63
64
65
66
67
68
69
     1
/ \
2 5
/ \ \
3 4 6

//将最左子节点的父节点和其右子节点断开
1
/ \
2 5
/ \
3 4 6

//将原左子节点连上父节点的右子节点
1
/ \
2 5
\ \
3 6

4

//把原右子节点连到新右子节点的右子节点
1
/ \
2 5
\ \
3 6
\
4

//回头上一级父节点(即为1)做相同的操作
1
/
2 5
\ \
3 6
\
4

||
_||_
\ /
\/

1
\
2 5
\ \
3 6
\
4

||
_||_
\ /
\/

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
34
35
36
37
38
39
40
41
42
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/


void flatten(struct TreeNode* root)
{
//root不为空即进入循环
while(root)
{
//如果左子树为NULL,则直接考虑下一个节点,将root跟新为其右孩子节点
if(!root->left)
{
root = root->right;
}
//寻找左子树最右边的节点
else
{
//新建一个辅助节点,指向根节点的左孩子节点
struct TreeNode* pre = root->left;
//将这个指针移动到左子树最右边的节点
while(pre->right)
{
pre = pre->right;
}

//将原来的右子树接到左子树的最右边节点
pre->right = root->right;
//将左子树插入到右子树的地方
root->right = root->left;
//将左子树置空
root->left = NULL;
//更新根节点
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
32
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/


void flatten(struct TreeNode* root)
{
if(!root) return;



if(root->left)
flatten(root->left);
if(root->right)
flatten(root->right);

//新建节点指向最左子节点的兄弟节点
struct TreeNode* tmp = root->right;
//断开最左子节点的右子节点并将左子节点接上
root->right = root->left;
root->left = NULL;
//遍历到新右子节点的末端
while(root->right)
root = root->right;
//将原右子节点接到新右子节点的最末端
root->right = tmp;
}

参考