一、题目描述：
给你二叉搜索树的根节点 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] 内
-231 <= Node.val <= 231 - 1
进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用 O(1) 空间的解决方案吗？
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/recover-binary-search-tree
二、思路分析：
一个合格的二叉搜索树的中序遍历一定是个严格递增的序列，如果发生了交换，可能会有两种情况：
交换的是相邻的节点，即发现一个节点值小于其前一个节点值时，这两个节点就刚好是被交换的。
交换的是不相邻的节点，即发现了两次异常，第一次是：A节点值大于其后一个节点值，第二次是：B节点值小于其前一个节点值。A和B就是被交换的两个节点。
首先，二叉搜索树的中序遍历出的节点是有序的
其次，并没有说交换的节点是相邻的，所以不能直接交换 pre->val 与 root->val
所以我们要找到两个不符合前一个节点值小于后一个节点值的点。
最后，将两节点交换。
过程：第一次找到（前大后小），由于x == nullptr,所以x = pre,之后的遍历都不会再对x产生影响，
只会改变y的值。
三、AC 代码：
class Solution {
public void recoverTree(TreeNode root) {
Deque<TreeNode> stk = new ArrayDeque<>();
TreeNode x = null, y = null, pre = null;
while (root != null || !stk.isEmpty()) {
while (root != null) {
stk.offer(root);
root = root.left;
}
root = stk.pollLast();
if (pre != null && pre.val > root.val) {
y = root;
if (x == null) {
x = pre;
} else {
break;
}
}
pre = root;
root = root.right;
}
// 交换节点
int tmp = x.val;
x.val = y.val;
y.val = tmp;
}
}
四、总结：
掘友们，解题不易，留下个赞或评论再走吧！谢啦~ 💐
希望对你有帮助
期待下次再见~
🌇 点赞 👍 收藏 ⭐留言 📝 一键三连 ~关注Jam，从你我做起！
