Flatten Binary Tree to Linked List
题目中给了提示可能用pre-order 来做。我们用一个prev来记录先序遍历中之前的点。
在递归过程中，保持先序遍历队形。
1
2
3
4
5
6
7
|
public void (TreeNode root) {
if (root == null)
return;
preorder(root.left);
preorder(root.right);
}
|
代码大致是这样一个结构。这题，我们要将prev的right改成prev的左子树，而prev的左子树得清空，所以我们得用变量来记录left和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
|
private TreeNode prev = null;
public void flatten(TreeNode root) {
if (root == null)
return;
helper(root);
}
private void (TreeNode root) {
if (root == null)
return;
if (prev == null)
prev = root;
else {
prev.right = root;
prev = root;
}
TreeNode left = root.left;
TreeNode right = root.right;
root.left = null;
preorder(left);
preorder(right);
}
|
近期评论