99.恢复二叉搜索树

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

示例 1：

img

1
2
3
输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    public void recoverTree(TreeNode root) {
        // 使用一个栈来支持中序遍历
        Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
        // x 和 y 是需要交换的两个节点
        TreeNode x = null, y = null, pred = null; // pred是当前节点的前一个节点（中序遍历中）
        // 使用迭代的方式进行中序遍历
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                // 首先访问最左侧节点
                stack.push(root);
                root = root.left;
            }
            // 访问栈顶元素，即当前最左侧的未访问节点
            root = stack.pop();
            // 检查当前节点与前一个节点的值，以确定是否这两个节点顺序错误
            if (pred != null && root.val < pred.val) {
                // 如果当前节点的值小于前一个节点的值，记录这两个节点
                y = root;
                if (x == null) {
                    // 第一次找到顺序错误的位置
                    x = pred;
                } else {
                    // 如果已经找到第一对，第二对则意味着完成了寻找
                    break;
                }
            }
            // 更新前一个节点为当前节点，继续遍历
            pred = root;
            root = root.right;
        }

        // 交换找到的两个节点的值来修正树
        swap(x, y);
    }

    // 交换两个节点的值
    public void swap(TreeNode x, TreeNode y) {
        int tmp = x.val;
        x.val = y.val;
        y.val = tmp;
    }
}