Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
題意：一個二叉查找樹(BST)有兩個節(jié)點被錯誤的交換放置了涝动，請恢復(fù)這顆BST.
例子：[1,2,3,4]這樣一個bst悲关，2是根節(jié)點陶冷，如果交換14，會變?yōu)閇4,2,3,1]，如果交換34柬焕，會變?yōu)閇1,2,4,3]。
思路：如果一個bst沒有被錯誤放置，那么中序遍歷的結(jié)果應(yīng)該是一個遞增序列●萌祝現(xiàn)在交換了其中兩個節(jié)點，從上面的例子我們能看到會出現(xiàn)1次或者2次的降序蹲嚣，因此我們只要中序遍歷這個bst递瑰，在遇到降序的時候祟牲，記錄下降序的節(jié)點隙畜。如果只有一次降序，要交換的兩個點就是這次降序的兩個節(jié)點说贝；如果出現(xiàn)了兩次降序议惰，那么第一個點是第一次降序的較大節(jié)點，第二個點是第二次降序的較小節(jié)點乡恕。
下面的中序遍歷用循環(huán)解法給出言询。
public void recoverTree(TreeNode root) {
if (root == null) {
return;
}
TreeNode swap1 = null;
TreeNode swap2 = null;
TreeNode pre = null;
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
if (pre != null && pre.val >= cur.val) {
if (swap1 == null) {
swap1 = pre;
swap2 = cur;
} else {
swap2 = cur;
}
}
pre = cur;
cur = cur.right;
}
int tmp = swap1.val;
swap1.val = swap2.val;
swap2.val = tmp;
}