原题
二叉搜索树中的两个节点被错误地交换。
请在不改变其结构的情况下，恢复这棵树。
示例 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/
相关推荐
-
leetcode410-分割数组的最大值
原题 给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。 注意:数组长度 n 满足以下条件: 1...
-
leetcode95-不同的二叉搜索树II
原题 给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？ 示例: 输入: 3 输出: [ [1,null,3,2], &n...
-
leetcode56-合并区间
原题 给出一个区间的集合，请合并所有重叠的区间。 示例 1: 输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]]...
-
海量数据算法-BitMap介绍和实现
作为一个有素质的程序员，在面试中（不是） 难免会遇到海量数据相关的问题，之前有注意过java.util下面有一个BitSet数据结构，但不是很明白是做什么用的。今天就来研究一下它背...
-
leetcode456-132模式
原题 给定一个整数序列：a1, a2, ..., an，一个132模式的子序列 ai, aj, ak 被定义为：当 i < j < k 时，ai < ak <...
-
leetcode28-实现strStr()
原题 实现 strStr() 函数。 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从...
-
剑指offer35-复杂链表的复制
原题（来源Leetcode） 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random ...
-
leetcode636-函数的独占时间
原题 给出一个非抢占单线程CPU的 n 个函数运行日志，找到函数的独占时间。 每个函数都有一个唯一的 Id，从 0 到 n-1，函数可能会递归调用或者被其他函数调用。 日志是具有以...
-
剑指offer64-求1+2+…+n
原题（来源Leetcode） 求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。 示例1...
-
leetcode283-移动零
原题 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。 示例: 输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 说...
