99. Recover Binary Search Tree

[Tcdian]

99. Recover Binary Search Tree

二叉搜索树中的两个节点被错误地交换。

请在不改变其结构的情况下，恢复这棵树。

Example 1

Input: [1,3,null,null,2]

   1
  /
 3
  \
   2

Output: [3,1,null,null,2]

   3
  /
 1
  \
   2

Example 2

Input: [3,1,4,null,null,2]

  3
 / \
1   4
   /
  2

Output: [2,1,4,null,null,3]

  2
 / \
1   4
   /
  3

[Tcdian]

Solution

• JavaScript Solution

/**
 * 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) {
    const nums = inorderTravel(root);
    const swapped = findSwapped(nums);
    dfs(root, swapped);

    function inorderTravel(root) {
        if (root === null) {
            return [];
        }
        const result = [];
        let patrol = root;
        const stack = [];
        while (patrol !== null || stack.length !== 0) {
            while (patrol !== null) {
                stack.push(patrol);
                patrol = patrol.left;
            }
            patrol = stack.pop();
            result.push(patrol.val);
            patrol = patrol.right;
        }
        return result;
    }
    function findSwapped(nums) {
        let x = undefined;
        let y = undefined;
        for (let i = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                x = x === undefined ? nums[i] : x;
                y = nums[i + 1];
            }
        }
        return [x, y];
    }
    function dfs(root, swapped) {
        if (root === null) {
            return;
        }
        if (root.val === swapped[0]) {
            root.val = swapped[1];
        } else if (root.val === swapped[1]) {
            root.val = swapped[0];
        }
        dfs(root.left, swapped);
        dfs(root.right, swapped);
    }
};

• TypeScript Solution

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

/**
 Do not return anything, modify root in-place instead.
 */
function recoverTree(root: TreeNode | null): void {
    const nums = inorderTravel(root);
    const swapped = findSwapped(nums);
    dfs(root, swapped);

    function inorderTravel(root: TreeNode | null): number[] {
        if (root === null) {
            return [];
        }
        const result: number[] = [];
        let patrol: TreeNode | null = root;
        const stack: TreeNode[] = [];
        while (patrol !== null || stack.length !== 0) {
            while (patrol !== null) {
                stack.push(patrol);
                patrol = patrol.left;
            }
            patrol = stack.pop() as TreeNode;
            result.push(patrol.val);
            patrol = patrol.right;
        }
        return result;
    }
    function findSwapped(nums: number[]): [number, number] {
        let x: number | undefined = undefined;
        let y: number | undefined = undefined;
        for (let i = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                x = x === undefined ? nums[i] : x;
                y = nums[i + 1];
            }
        }
        return [x as number, y as number];
    }
    function dfs(root: TreeNode | null, swapped: [number, number]) {
        if (root === null) {
            return;
        }
        if (root.val === swapped[0]) {
            root.val = swapped[1];
        } else if (root.val === swapped[1]) {
            root.val = swapped[0];
        }
        dfs(root.left, swapped);
        dfs(root.right, swapped);
    }
};