前言
本周终于完成了一道困难题！！！
恢复二叉搜索树
二叉搜索树中的两个节点被错误地交换。
请在不改变其结构的情况下，恢复这棵树。
示例 1:
示例 2:
题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/recover-binary-search-tree
先放我的代码：
/**
* 力扣中关于二叉树的默认定义
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
TreeNode one = null; //逆序中大的值
TreeNode two = null; //逆序中小的值
TreeNode pre = null; //上一个节点
int temp;
public void recoverTree(TreeNode root) {
order(root); //中序遍历找出逆序的两个数
temp = one.val;
one.val = two.val;
two.val = temp;
}
public void order(TreeNode root){
if(root==null) return;
if(root.left!=null){
order(root.left);
}
if(pre!=null && pre.val > root.val){
if(one==null){
one=pre;
two=root;
}
else{
two=root;
}
}
pre=root;
if(root.right!=null){
order(root.right);
}
}
}
又是一道二叉树问题，做了几道后发现二叉树问题一般都是可以用递归解决的，所以思路就很明确了，递归！！
通过之前对二叉树的了解我知道了二叉树的遍历有：
先序遍历，中序遍历，后序遍历，层次遍历。
而题目又说的很明确，二叉搜索树！！对于二叉搜索树，百度百科有很清晰的解释：
这样的话解法就很清晰了，中序遍历+递归。先递归到最小的一个节点，从这个节点开始判断，若这个节点前一个数大于当前节点就说明有冲突，这两个数就是我们要找的数了。然鹅梦想是美好的现实是残酷的，没这么简单，我的想法仅限于相邻的两个数之间的交换，不得已看了一下官方题解，发现两个数冲突叫做逆序，而这个逆序有两种可能性，一种是相邻之间的逆序，一种是相隔几个数的逆序，前者会产生一组逆序的数字，后者会产生两组逆序的数组，因此需要在逆序那里多加一次判断，第一次逆序时把one赋给pre，也就是较大的值，root赋给two；第二次逆序时把root再次赋给two。如此一来，可以确保one里面存的就是大的那个数，two存的是小数。退出递归后
recoverTree方法仅仅是把one.val和two.val交换即可恢复二叉搜索树。欢迎访问我的博客www.redmango.top
