99. 恢复二叉搜索树 - 力扣（LeetCode）

一、题目

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

进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用 O(1) 空间的解决方案吗？

示例 1：

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

示例 2：

输入：root = [3,1,4,null,null,2]
输出：[2,1,4,null,null,3]
解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。

提示：

• 树上节点的数目在范围 [2, 1000] 内
• -231 <= Node.val <= 231 - 1

二、代码

方法一（时间复杂度O(N)，额外空间复杂度O(树的高度)） 

class Solution {// 时间复杂度O(N)，空间复杂度O(树的高度)public void recoverTree(TreeNode root) {// 用来记录所需要的两个降序位置// ans[0]:表示第一次降序的第一个节点// ans[1]:表示最后一次降序的第二个节点（如果只有一次降序，那么这个就是唯一这一次降序的第二个节点）// 通过中序序列得到我们需要的降序位置TreeNode[] ans = in(root);TreeNode s1;TreeNode s2;// 将找到的两个位置交换即可完成恢复if (ans[0] != null && ans[1] != null) {int temp = ans[0].val;ans[0].val = ans[1].val;ans[1].val = temp;}}// 通过非递归版本的中序遍历找到我们需要的两个降序位置public TreeNode[] in(TreeNode root) {// 当前遍历到的节点TreeNode cur = root;// 要返回的答案TreeNode[] ans = new TreeNode[2];// 标记当前是否找到了降序位置（用来标记是第一次找到降序位置还是第二次找到降序位置）boolean flag = false;// 记录中序序列的上一个节点，一开始设置为系统最小值TreeNode pre = new TreeNode(Integer.MIN_VALUE);// 用来实现非递归的中序遍历Stack stack = new Stack<>();while (cur != null || !stack.isEmpty()) {if (cur != null) {stack.push(cur);cur = cur.left;} else {cur = stack.pop();// 当前位置的值小于中序序列的上一个值，说明找到了降序// 如果flag==false，说明这个是找到的第一次降序if (cur.val < pre.val && !flag) {// 记录第一次降序的第一个位置ans[0] = pre;// 设置为trueflag = true;} // 这里不能用else if，因为有可能出现的两次降序是连在一起的。或者如果只有一次降序的话，还需要记录这一次降序的第二个位置// flag == true表示这是第二次降序if (cur.val < pre.val && flag) {// 记录最后一次降序的第二个位置ans[1] = cur;}// 更新中序序列的上一个节点pre = cur;cur = cur.right;}}return ans;}
}

方法二（时间复杂度O(N)，额外空间复杂度O(1)）  

class Solution {// 时间复杂度O(N)，空间复杂度O(1)public void recoverTree(TreeNode root) {// 用来记录所需要的两个降序位置// ans[0]:表示第一次降序的第一个节点// ans[1]:表示最后一次降序的第二个节点（如果只有一次降序，那么这个就是唯一这一次降序的第二个节点）// 通过中序序列得到我们需要的降序位置TreeNode[] ans = in(root);TreeNode s1;TreeNode s2;// 将找到的两个位置交换即可完成恢复if (ans[0] != null && ans[1] != null) {int temp = ans[0].val;ans[0].val = ans[1].val;ans[1].val = temp;}}// 通过非递归版本的中序遍历找到我们需要的两个降序位置public TreeNode[] in(TreeNode root) {// 当前遍历到的节点TreeNode cur = root;// 要返回的答案TreeNode[] ans = new TreeNode[2];// 标记当前是否找到了降序位置（用来标记是第一次找到降序位置还是第二次找到降序位置）boolean flag = false;// 记录中序序列的上一个节点，一开始设置为系统最小值TreeNode pre = new TreeNode(Integer.MIN_VALUE);// 当前节点左树上的最右节点TreeNode leftTreeMostRightNode = null;// Morris遍历改中序遍历while (cur != null) {leftTreeMostRightNode = cur.left;if (leftTreeMostRightNode != null) {while (leftTreeMostRightNode.right != null && leftTreeMostRightNode.right != cur) {leftTreeMostRightNode = leftTreeMostRightNode.right;}if (leftTreeMostRightNode.right == null) {leftTreeMostRightNode.right = cur;cur = cur.left;continue;} else {leftTreeMostRightNode.right = null;}}// 当前位置的值小于中序序列的上一个值，说明找到了降序// 如果flag==false，说明这个是找到的第一次降序if (cur.val < pre.val && !flag) {// 记录第一次降序的第一个位置ans[0] = pre;// 设置为trueflag = true;} // 这里不能用else if，因为有可能出现的两次降序是连在一起的。或者如果只有一次降序的话，还需要记录这一次降序的第二个位置// flag == true表示这是第二次降序if (cur.val < pre.val && flag) {// 记录最后一次降序的第二个位置ans[1] = cur;}// 更新中序序列的上一个节点pre = cur;cur = cur.right;}return ans;}
}

三、解题思路 

这道题首先我们要知道搜索二叉树的一些性质，搜索二叉树的中序遍历应该是一个升序的序列。只要不是升序，就说明这个不是搜索二叉树。我们就基于这个性质，来求解这道题。

可能有两对或一对降序：第一个错误节点是第一回降序的第一个节点， 第二个错误节点是最后一回降序的第二个节点（这个是通过观察法的得来的，自己列出几个例子，然后就可以发现这个规律了）。把错误节点交换值即可完成恢复。

这道题可以直接在中序遍历的过程中找到降序位置，然后收集我们需要的两个数。这种写法的空间复杂度是O(树的高度)。这道题还可以在不影响时间复杂度的情况下将空间复杂度优化成O(1)，可以采用Morris遍历就可以实现。