99 Recover Binary Search Tree

99. Recover Binary Search Tree

1. Question

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:

A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

2. Implementation

(1) Iteration

class Solution {
    public void recoverTree(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curNode = root;
        TreeNode preNode = null, firstNode = null, secondNode = null;

        while (curNode != null || !stack.isEmpty()) {
            if (curNode != null) {
                stack.push(curNode);
                curNode = curNode.left;
            }
            else {
                curNode = stack.pop();
                if (preNode != null && preNode.val > curNode.val) {
                    if (firstNode == null) {
                        firstNode = preNode;
                    }
                    secondNode = curNode;
                }
                preNode = curNode;
                curNode = curNode.right;
            }
        } 

        if (firstNode != null && secondNode != null) {
            int temp = firstNode.val;
            firstNode.val = secondNode.val;
            secondNode.val = temp;
        }
    }
}

(2) Recursion

class Solution {
    public void recoverTree(TreeNode root) {
        TreeNode[] nodes = new TreeNode[3];

        inorderTraverse(root, nodes);

        int temp = nodes[1].val;
        nodes[1].val = nodes[2].val;
        nodes[2].val = temp;
    }

    public void inorderTraverse(TreeNode node, TreeNode[] nodes) {
        if (node == null) {
            return;
        }

        inorderTraverse(node.left, nodes);

        TreeNode preNode = nodes[0];

        if (preNode != null && preNode.val >= node.val) {
            if (nodes[1] == null) {
                nodes[1] = preNode;
            }
            nodes[2] = node;
        }

        nodes[0] = node;

        inorderTraverse(node.right, nodes);
    }
}

3. Time & Space Complexity

Iteration: 时间复杂度: O(n), 空间复杂度: O(h)

Recursion: 时间复杂度: O(n), 空间复杂度: O(h)