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 {
private TreeNode lastVisited = null, x = null, y = null;
public void recoverTree(TreeNode root) {
dfs(root);
swap(x, y);
}
private void dfs(TreeNode root) {
if (root == null) {
return;
}
dfs(root.left);
if (lastVisited != null && root.val < lastVisited.val) {
y = root;
if (x == null) {
x = lastVisited;
} else {
return;
}
}
lastVisited = root;
dfs(root.right);
}
private void swap(TreeNode nodeOne, TreeNode nodeTwo) {
int temp = nodeOne.val;
nodeOne.val = nodeTwo.val;
nodeTwo.val = temp;
}
}
|
这道题告诉我们在一个sorted list中, 两个元素交换了位置, 我们如何找到这两个元素的办法. 大致的思路就是被换到前面的大的数, 它的后一个数字肯定比自己小, 而换到后面的小数, 它比它的前一个小. 我们就利用这个特点来去找. 14行遇到现在比前一个数字小的情况, 那这有两种情况, 要么是我们先来到了换到前面的大数的后一个位置, 此时我们前一个位置就是大数; 或者是我们来到了小数的位置. 如何区别这两种情况呢? 我们统一认为我们现在是小数的位置, 让y = 现在的位置的数字. 然后看x是否有值, 如果有的话就说明之前已经找到了大数并存到了x中, 那么此时我们确实就是小数的位置, 直接return即可. 如果x是null, 那说明我们在大数后一个位置, 那么让x等于我们前一个位置的值, 此时还要继续找那个小数在哪里. 此时y存的值并一定是小数的值, 因为可能两个背靠背的数字交换了.
还有就是如何用栈来iterative inorder traversal.
最后就是不要用Stack类而是Deque类, new一个ArrayDeque. 因为后者提供了更全面的功能. Queue用Deque也挺好.
时间复杂度: 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
26
27
28
29
30
31
| class Solution {
private TreeNode lastVisited = null, x = null, y = null;
public void recoverTree(TreeNode root) {
Deque<TreeNode> stack = new ArrayDeque<>();
while (!stack.isEmpty() || root != null) {
while (root != null) {
stack.push(root);
root = root.left;
}
TreeNode currNode = stack.pop();
if (lastVisited != null && currNode.val < lastVisited.val) {
y = currNode;
if (x == null) {
x = lastVisited;
} else {
break;
}
}
lastVisited = currNode;
root = currNode.right;
}
swap(x, y);
}
private void swap(TreeNode nodeOne, TreeNode nodeTwo) {
int temp = nodeOne.val;
nodeOne.val = nodeTwo.val;
nodeTwo.val = temp;
}
}
|
Iterative 版本, 其实就是模仿栈的工作, 先疯狂压左边, 等到左边是null的时候, pop出来一个, 然后在走右边一个node, 同样疯狂压右边node的左边.
时间复杂度和空间复杂度不变.
