原题
二叉搜索树中的两个节点被错误地交换。
请在不改变其结构的情况下，恢复这棵树。
示例 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/
