leetcode-javascript/solutions/0099-recover-binary-search-tree.js at development · Anuj9826/leetcode-javascript · GitHub

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
/**
 * Recover Binary Search Tree
 * Time Complexity: O(N)
 * Space Complexity: O(H)
*/
var recoverTree = function (root) {
    let firstViolationCandidate = null;
    let secondViolationCandidate = null;
    let previousNodeInOrder = null;

    const performInOrderTraversal = (currentTreeRoot) => {
        if (!currentTreeRoot) {
            return;
        }

        performInOrderTraversal(currentTreeRoot.left);

        if (previousNodeInOrder !== null && previousNodeInOrder.val > currentTreeRoot.val) {
            if (firstViolationCandidate === null) {
                firstViolationCandidate = previousNodeInOrder;
            }
            secondViolationCandidate = currentTreeRoot;
        }

        previousNodeInOrder = currentTreeRoot;

        performInOrderTraversal(currentTreeRoot.right);
    };

    performInOrderTraversal(root);

    const temporaryValue = firstViolationCandidate.val;
    firstViolationCandidate.val = secondViolationCandidate.val;
    secondViolationCandidate.val = temporaryValue;
};