Skip to content

99. Recover Binary Search Tree

https://leetcode.com/problems/recover-binary-search-tree/

js
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var recoverTree = function(root) {
    const nodes = traverseTree(root)
    const mistakes = []
    for (let i = 1; i < nodes.length; i++) {
        if (nodes[i - 1].val > nodes[i].val) {
            if (mistakes.length === 0) {
                mistakes.push({ index: i - 1, node: nodes[i - 1] })
            } else {
                mistakes.push({ index: 1, node: nodes[i] })
            }

        }
    }
    if (mistakes.length < 2) {
        swapNode(mistakes[0].node, nodes[mistakes[0].index + 1])
    } else {
        swapNode(mistakes[0].node, mistakes[1].node)
    }
};

function swapNode(node1, node2) {
    const temp = node1.val
    node1.val = node2.val
    node2.val = temp
}

function traverseTree(root) {
    let nodes = []

    if (!root) {
        return nodes
    }

    nodes = nodes.concat(traverseTree(root.left))
    nodes.push(root)
    nodes = nodes.concat(traverseTree(root.right))

    return nodes
}