题目描述

给你二叉搜索树的根节点 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); }
}