[数据结构与算法]恢复二叉搜索树

题目描述

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

示例：

• 输入：root = [1,3,null,null,2]
• 输出：[3,1,null,null,2]
• 解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/recover-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：中序遍历

首先一个二叉搜索树的中序遍历是从小到大递增的。对于这种交换了两个值得二叉树，得出的中序遍历会有两种情况。
1. 1 3 2 4 5 ，这种情况是3->2出现一次逆序，其他没有出现逆序。我们交换第一次出现逆序的前元素和后元素即可。
2. 1 4 3 2 5 ，这种情况是4->3出现一次逆序，3->2出现一次逆序。我们交换第一次初选逆序的前元素和第二次出现逆序的后元素，交换即可。

class Solution {
    TreeNode x=null;
    TreeNode y=null;
    TreeNode pre=null;
    public void recoverTree(TreeNode root) 
    {
        dfs(root);
        int temp=x.val;   //交换两个节点的值
        x.val=y.val;
        y.val=temp;
    }
    void dfs(TreeNode node)
    {
        if(node.left!=null)
            dfs(node.left);
        if(pre!=null&&pre.val>node.val) 
        {
            if(y==null)        //第一次逆序，要保存前元素
                x=pre;
            y=node;            //两种情况都要保存后元素
        }
        pre=node;
        if(node.right!=null)
            dfs(node.right); 
    }
}