99. Recover Binary Search Tree

Link

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

Recover the tree without changing its structure.

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

Follow up:

• A solution using O(n) space is pretty straight forward.

• Could you devise a constant space solution?

Solution

首先想到inorder traversal去找出問題的點的做法 觀察到第一個出問題的點會比下一個大 第二個出問題的點會比上一個小 ex. 6, 2,3,4,5, 1 其中第一個點就是6，第二個點就是1 只要swap 6, 1就可以recover

class Solution {
    public void recoverTree(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode previousNode = null;
        TreeNode firstElement = null, secondElement = null;
        while(root != null || !stack.isEmpty()){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            TreeNode node = stack.pop();
            //Travlsa to get the weird the node
            if(previousNode != null && node.val < previousNode.val){
                //need swap
                if(firstElement == null){
                    firstElement = previousNode;
                    secondElement = node;
                }
                else{
                    secondElement = node;
                    break;
                }
               
            }
            previousNode = node;
            root = node.right;
        }
        //swap
        int temp = secondElement.val;
        secondElement.val = firstElement.val;
        firstElement.val = temp;
    }
}

T: O(N)

S: 但空間複雜度會根據stack大小應該是O(N) 若希望空間複雜度可以O(1) 那要用mirrior traversal的做法，目前沒時間準備先這樣。