Leetcode力扣秋招刷题路-0099

从0开始的秋招刷题路，记录下所刷每道题的题解，帮助自己回顾总结

99. 恢复二叉搜索树

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

示例 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] 内
$-2^{31}$ <= Node.val <= $2^{31}-1$

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

思路
因为只有两个节点错误，所以只要找出这两个节点然后交换值即可。

BST中序遍历是升序结果，因此进行中序遍历，使用三个指针指示节点，cur为当前节点，pre为当前节点之前的节点，wrongNode为错误节点

当当前节点小于上一个节点时，上一个节点pre就是第一个错误节点，用wrongNode记录，然后继续遍历，找出第二个错误节点， 这里有两种情况：

1.当当前节点大于wrongNode时，它的前节点就是第二个错误节点，如[1,3,2,4]，错误节点分别为3、2

2.遍历结束时仍然没有节点大于wrongNode，则最后一个节点就是错误节点，如[3,1,2]，错误节点为3、2

public void recoverTree(TreeNode root) {if (root == null) return;Stack<TreeNode> stack = new Stack<>();TreeNode pre = null, cur = root, wrongNode = null;while (!stack.isEmpty() || cur != null) {if (cur != null) {stack.add(cur);cur = cur.left;} else {cur = stack.pop();//与上一个节点比较，找到错误节点if (wrongNode == null && pre != null && cur.val < pre.val) {wrongNode = pre;}//表示当前节点是否大于wrongNodeif (wrongNode != null && cur.val > wrongNode.val) {swap(pre, wrongNode);break;}pre = cur;cur = cur.right;}}//如果没有节点大于wrongNode，与最后一个节点交换值if (wrongNode != null && wrongNode.val > pre.val) {swap(pre, wrongNode);}
}private void swap(TreeNode pre, TreeNode wrongNode) {int tmp = pre.val;pre.val = wrongNode.val;wrongNode.val = tmp;
}