恢复二叉搜索树

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

示例 1：

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

1
2
3

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var recoverTree = function(root) {

    let perv = new TreeNode(-Infinity);
    let err1, err2 = null;

    const inOrder = (root) => {
        if (root == null) {
            return;
        }
        inOrder(root.left);

        if (perv.val >= root.val && err1 == null) { // 当前是第一对错误
            err1 = perv;                            // 记录第一个错误点
        }
        if (perv.val >= root.val && err1 != null) { // 第一个错误点已确定
            err2 = root;                            // 记录第二个错误点
        }
        perv = root;       // 更新 perv

        inOrder(root.right);
    };

    inOrder(root);
    const temp = err1.val;
    err1.val = err2.val;
    err2.val = temp;

};

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

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/recover-binary-search-tree

← 验证二叉搜索树相同的树→