leetcode java_Recover Binary Search Tree[恢复二进制搜索树]

　　Recover Binary Search Tree

　　leetcode 原题链接：https://leetcode.com/problems/recover-binary-search-tree/

　　题目如图所示：

　　与Valid BST的那个题相似，那个是要验证一个树是否valid，这个是已经知道这是一个invalid的BST了，需要纠错。那么，还是从inorder traversal出发，因为inorder traversal可以得到一个升序的数列。那么，找到其中不合群的两个数，交换方能得解。

　　这里有一点需要注意，假如有一个升序的数列：

　　1,2,3,4,5,6,7,8,9

　　其中有两个数的位置错了：

　　1,2,7,4,5,6,3,8,9

　　那么，当从头开始向后数，走到7的时候，4 <7，就说明7与4这个组合有问题，再继续向后走，发现6与3这个组合有问题。那么怎么确定是在这两组数里面，那两个数是错误的呢?

　　先看第一组，因为7之前的数都是排列正确的，7突然变大，说明7是从后面交换过来的。同理，在第二组中，3是突然变小的数，那么，说明3是从前面交换过来的。那么就可以确定，第一组里面的第一个数，和第二组里面第二个数相互交换了位置。看代码：

　　public class Solution {
　　TreeNode pre = null;
　　TreeNode first = null;
　　TreeNode second = null;
　　public void recoverTree(TreeNode root) {
　　inorder(root);
　　int tmp = first.val;
　　first.val = second.val;
　　second.val = tmp;
　　}
　　public void inorder(TreeNode root){
　　if(root == null){
　　return;
　　}
　　inorder(root.left);
　　if(pre != null && pre.val > root.val){
　　if(first == null){
　　first = pre;
　　}
　　second = root;
　　}
　　pre = root;
　　inorder(root.right);
　　}
　　}