原题
二叉搜索树中的两个节点被错误地交换。
请在不改变其结构的情况下，恢复这棵树。
示例 1:
输入: [1,3,null,null,2]
1
/
3
\
2输出: [3,1,null,null,2]
3
/
1
\
2
示例 2:
输入: [3,1,4,null,null,2]
3
/ \
1 4
/
2输出: [2,1,4,null,null,3]
2
/ \
1 4
/
3
进阶:
- 使用 O(n) 空间复杂度的解法很容易实现。
- 你能想出一个只使用常数空间的解决方案吗？
解法
思想
这道题可以使用中序遍历得到一个序列，这个序列的特征是一个有序序列中的两个元素被交换了，那么问题就变成如何找到这两个元素。
看一个例子： 1 2 8 6 7 4 9 ，有序序列中的两个元素被交换了一定会造成一个较大的元素交换到了前面(8)，一个较小的元素交换到了后面(4)，体现在序列中就是两个异常的情况：6比8小，4比7小。所以可以判断：第一次出现的某节点比前驱节点的值要小的情况，前驱节点就是一个被交换了的节点，而第二次出现的某节点比前驱节点的值要小的情况，该节点就是第二个被交换了的节点。
而还有一种可能是，两个连续的元素被交换了，如：1 3 2 4，出现的情况就是只出现一次某节点比前驱节点的值要小的情况，那么两个被交换的节点就分别是当前节点(2)和其前驱节点(3)。
找到了这两个节点，就可以使用值交换将二叉搜索树恢复回来。
代码
递归中序遍历：
class Solution {
TreeNode pred;
TreeNode former,latter;
public void recoverTree(TreeNode root) {
recurTree(root);
int cache = former.val;
former.val = latter.val;
latter.val = cache;
}
public void recurTree(TreeNode root){
if(root == null) return;
recurTree(root.left);
if(pred == null) pred = root;
else if(root.val < pred.val) {
if(former == null) former = pred;
latter = root;
}
pred = root;
recurTree(root.right);
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode99-%e6%81%a2%e5%a4%8d%e4%ba%8c%e5%8f%89%e6%90%9c%e7%b4%a2%e6%a0%91/
相关推荐
-
leetcode108-将有序数组转换为二叉搜索树
原题 将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 示例: 给定有序数...
-
剑指offer50-第一个只出现一次的字符
原题（来源Leetcode） 在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。 示例: s = "abaccdeff" 返回 "b" s...
-
leetcode328-奇偶链表
原题 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。 请尝试使用原地算法完成。你的算法的空...
-
leetcode403-青蛙过河
原题 一只青蛙想要过河。 假定河流被等分为 x 个单元格，并且在每一个单元格内都有可能放有一石子（也有可能没有）。 青蛙可以跳上石头，但是不可以跳入水中。 给定石子的位置列表（用单...
-
leetcode1162-地图分析
原题 你现在手里有一份大小为 N x N 的『地图』（网格） grid，上面的每个『区域』（单元格）都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，你知道距离陆地区域...
-
leetcode56-合并区间
原题 给出一个区间的集合，请合并所有重叠的区间。 示例 1: 输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]]...
-
leetcode680-验证回文字符串II
原题 给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。 示例 1: 输入: "aba" 输出: True 示例 2: 输入: "abca" 输出: True 解...
-
leetcode167-两数之和II-输入有序数组
原题 给定一个已按照 升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。 函数应该返回这两个下标值index1和index2，其中index1必须小于index2。 说明...
-
leetcode75-颜色分类
原题 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。 此题中，我们使用整数 0、 1 和 2 分...
-
leetcode191-位1的个数
原题 编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。 示例 1： 输入： 000000000000000000000000...
