Leetcode--Java--99. 恢复二叉搜索树

给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。

中序遍历 + 降序对判断
核心思路：直接找错误的两个结点node1和node2进行交换，中序遍历过程中记录当前结点的前一个结点pre。

1. 错误类型就两种：一种是相邻的逆序对，直接找到两个交换即可。另一种是有多个逆序对，要找到第一次逆序对的前一个结点为node1，最后一次逆序对的后一个结点为node2，交换这两结点就行。
   
2. 综合上面两种错误类型，可以知道前一次和最后一次可能为同一次，所以在判断node1的时候注意是否已经出现过。

class Solution {
      TreeNode node1 = null, node2 = null, pre = null;
    public void recoverTree(TreeNode root) {
       findErrorNode(root);
       //交换两个错误结点
       int t = node1.val;
       node1.val = node2.val;
       node2.val = t;
    }
    //中序遍历寻找错误的两个结点
    public void findErrorNode(TreeNode root) {
        if (root == null) return;
        findErrorNode(root.left);
        // 如果pre不为空，并且当前结点小于前一个结点
        if (pre != null && root.val < pre.val) {
            //判断是否已经找到了第一个错误结点，没找到才赋值  （因为有两种错误类型）
            if (node1 == null) {
                node1 = pre;
            }
            node2 = root;
        }
        //根结点赋值给前一个结点
        pre = root;
        findErrorNode(root.right);
    }
}