Recover Binary Search Tree

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

Recover the tree without changing its structure.

Analysis

in-order traversal

private void traverse (TreeNode root) {
   if (root == null)
      return;
   traverse(root.left);
   // Do some business to root
   traverse(root.right);
}

假设有以下tree需要swap:

          7
        /   \
       2    10
      / \  /  
     1  8  5

• 按照in-order traverse 的顺序，会按照以下顺序"do some business"
  • 1->2->8->7->5->10
• 当发现8>7时，说明8是1st node需要swap
• 当发现7>5时，说明5是2nd node需要swap
• 建立3个global的treeNode来存需要swap的node的地址，traversal后swap

Code

public class Solution {

    TreeNode first = null;
    TreeNode second = null;
    // The reason for this initialization is to avoid null pointer exception in the first comparison when prevElement has not been initialized
    TreeNode prev = new TreeNode(Integer.MIN_VALUE);

    public void recoverTree(TreeNode root) {

        // In order traversal to find the two elements
        traverse(root);

        // Swap the values of the two nodes
        int temp = first.val;
        first.val = second.val;
        second.val = temp;
    }

    private void traverse(TreeNode root) {

        if (root == null)
            return;

        traverse(root.left);

        // Start of "do some business", 

        //Condition for find 1st swap node, root->7
        if (first ==null && prev.val > root.val){
            first = prev;
        }

        //Condition for find 2nd swap node, root->5
        if (first !=null && prev.val > root.val){
            second = root;
        }


        //每次都把root存到prevElement里，用来和下一个in-order traversal指向的node比较
        //注意这个要放在第一次比较的后面，用Integer.MIN_VALUE去和第一个node‘1’比较
        prev = root;


        // End of "do some business"

        traverse(root.right);
}

Reference

Leetcode