Given a binary tree, flatten it to a linked list in-place.
For example, given the following tree:
1
2
3
4
5
| 1
/ \
2 5
/ \ \
3 4 6
|
The flattened tree should look like:
1
2
3
4
5
6
7
8
9
10
11
| 1
\
2
\
3
\
4
\
5
\
6
|
1 递归
思路简单, 实现起来比较复杂.
flatten一个树, 等于先flatten两个子树, 然后再将两个子树合起来, 合起来的时候, flatten过的左子树在前, 右子树在后.
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
|
class Solution {
public void flatten(TreeNode root)
{
if(root == null)
return;
flatten(root.left);
flatten(root.right);
TreeNode tmp = root.right;
root.right = root.left;
TreeNode iterator = root;
while(iterator.right != null)
iterator = iterator.right;
iterator.right = tmp;
root.left = null;
}
}
|
2 迭代
贴一个leetcode官网上的方法,这个方法太赞了, 空间复杂度只有O(1).
https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/solution/er-cha-shu-zhan-kai-wei-lian-biao-by-leetcode-solu/
注意到前序遍历访问各节点的顺序是根节点、左子树、右子树。如果一个节点的左子节点为空，则该节点不需要进行展开操作。如果一个节点的左子节点不为空，则该节点的左子树中的最后一个节点被访问之后，该节点的右子节点被访问。该节点的左子树中最后一个被访问的节点是左子树中的最右边的节点，也是该节点的前驱节点。因此，问题转化成寻找当前节点的前驱节点。
具体做法是，对于当前节点，如果其左子节点不为空，则在其左子树中找到最右边的节点，作为前驱节点，将当前节点的右子节点赋给前驱节点的右子节点，然后将当前节点的左子节点赋给当前节点的右子节点，并将当前节点的左子节点设为空。对当前节点处理结束后，继续处理链表中的下一个节点，直到所有节点都处理结束。
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
|
class Solution {
public void flatten(TreeNode root)
{
TreeNode curr = root;
while(curr != null)
{
TreeNode tmp = curr.right;
TreeNode leftNode = curr.left;
if(leftNode == null)
{
curr = curr.right;
continue;
}
while(leftNode.right != null)
{
leftNode = leftNode.right;
}
leftNode.right = tmp;
curr.right = curr.left;
curr.left = null;
curr = curr.right;
}
}
}
|