Recover Binary Search Tree
给一个bst, 里面有两个node互换了. 找出并且换回. 因为是bst, 所以要利用bst的性质找两个node.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
TreeNode first = null;
TreeNode second = null;
TreeNode last = new TreeNode(Integer.MIN_VALUE);
public void recoverTree(TreeNode root) {
if(root == null)
return;
rec(root);
int tmp = first.val;
first.val = second.val;
second.val = tmp;
}
public void rec(TreeNode root) {
if(root == null)
return;
rec(root.left);
if(first == null && last.val > root.val)
first = last;
if(first != null && last.val > root.val)
second = root;
last = root;
rec(root.right);
}
}