LC99. Recover Binary Search Tree
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的两个节点错了，怎样恢复？
Recursion solution:
BST的inorder traversal是升序的，所以利用三个全局变量，中序遍历这棵树。由于升序，所以肯定是大的出现在前面，小的出现在后面。所以第一次发现pre > cur，说明pre就是node1，同理第二次pre > cur，说明cur是node2。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
TreeNode node1 = null, node2 = null;
TreeNode pre = new TreeNode(Integer.MIN_VALUE);
public void recoverTree(TreeNode root) {
if(root == null) return;
travel(root);
int t = node1.val;
node1.val = node2.val;
node2.val = t;
return;
}
private void travel(TreeNode node){
if(node == null) return;
travel(node.left);
if(node1 == null && pre.val >= node.val){
node1 = pre;
}
if(node1 != null && pre.val >= node.val){
node2 = node;
}
pre = node;
travel(node.right);
}
}
O(n), O(height). 递归的空间是树的高度_(:з」∠)_
…递归的空间是树的高度这还是学长告诉的可我面试没过…TAT
Iteration solution:
同理利用3个变量和inorder traversal。重点是Morris Treversal 这是一种常数空间的遍历方法，不需要利用栈存节点，blog和vidio都讲的挺清楚的, 对于先序，中序，后序都只需要很小的改动即可实现。重点是在遍历的时候将叶子的左或者右指向前驱或后继节点。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
TreeNode node1 = null, node2 = null;
TreeNode pre = new TreeNode(Integer.MIN_VALUE);
public void recoverTree(TreeNode root) {
// inorder mirris traversal -> O(n), O(1)
TreeNode temp = null;
while(root != null){
if(root.left != null){
temp = root.left;
while(temp.right != null && temp.right != root) temp = temp.right;
if(temp.right != null){
if(pre.val >= root.val){
if(node1 == null) node1 = pre;
node2 = root;
}
pre = root;
temp.right = null;
root = root.right;
}else{
temp.right = root;
root = root.left;
}
}else{
if(pre.val >= root.val){
if(node1 == null) node1 = pre;
node2 = root;
}
pre = root;
root = root.right;
}
} // while
if(node1 != null && node2 != null){
int t = node1.val;
node1.val = node2.val;
node2.val = t;
}
}
}
O(n), O(1)
最后只需要交换两个节点的值即可。