给定一个二叉树，原地将它展开为一个单链表。
例如，给定二叉树
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
|
方法一：前序遍历
将二叉树展开为单链表后，我们发现链表中元素的顺序和二叉树的先序遍历结果相同， 在二叉树先序遍历时，我们使用一个数组存储遍历到的结点，最后将数组中相邻元素连接起来。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public void flatten(TreeNode root) {
List<TreeNode> list = new ArrayList<>();
preorderTraversal(root, list);
int size = list.size();
for(int i = 1; i < size; i++){
TreeNode prev = list.get(i - 1);
TreeNode cur = list.get(i);
prev.left = null;
prev.right = cur;
}
}
public void preorderTraversal(TreeNode root, List<TreeNode> list){
if(root != null){
list.add(root);
preorderTraversal(root.left, list);
preorderTraversal(root.right, list);
}
}
}
|
时间复杂度O(n)，每个结点访问两次。空间复杂度O(n)，数组中存储 n 个结点。
方法二：递归
我们知道前序遍历的顺序为“根 - 左 - 右”，我们反过来先将右子树变为链表，再将左子数变为链表，再将左子树链表的末尾连接上右子树链表的头部，最后将根节点右结点连接到左子树链表头部，将根节点左结点置空。
我们使用一个全局变量 last 来保存已经生成的链表的头部，从链表尾部到头部，递归地生成链表。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
private TreeNode last = null;
public void flatten(TreeNode root) {
if(root == null){
return;
}
flatten(root.right);
flatten(root.left);
root.right = last;
root.left = null;
last = root;
}
}
|
时间复杂度O(n)，空间复杂度O(n)。
方法三：寻找前驱结点
我们可以发现前序遍历中，左子树的最右结点下一个结点就为右结点，我们可以将右子树作为左子树前序遍历最后一个结点的右子树，这样就可以保持前序遍历不变。然后再将左子树变成右子树，左子树置空。我们对二叉树中所有结点做这样一个操作，就可以将二叉树变成链表。
以示例为例
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
| class Solution {
public void flatten(TreeNode root) {
TreeNode cur = root;
while(cur != null){
if(cur.left != null){
TreeNode leftLast = cur.left;
while(leftLast.right != null){
leftLast = leftLast.right;
}
leftLast.right = cur.right;
cur.right = cur.left;
cur.left = null;
}
cur = cur.right;
}
}
}
|
时间复杂度O(n)，空间复杂度O(1)。