Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

Naive Way: A recursive method just came to my mind. Keep finding the middle element as root and recursive on both half.

 /**  
  * Definition for binary tree  
  * public class TreeNode {  
  *   int val;  
  *   TreeNode left;  
  *   TreeNode right;  
  *   TreeNode(int x) { val = x; }  
  * }  
  */  
 public class Solution {  
   public TreeNode sortedArrayToBST(int[] num) {  
     return sortedArrayToBST(num, 0, num.length-1);  
   }  
   public TreeNode sortedArrayToBST(int[] num, int begin, int end){  
     // base case  
     if(begin > end) return null;  
     // recursion  
     int middle = (begin+end)/2;  
     TreeNode root = new TreeNode(num[middle]);  
     root.left = sortedArrayToBST(num, begin, middle-1);  
     root.right = sortedArrayToBST(num, middle+1, end);  
     return root;  
   }  
 }  

Improved Way: As long as there is a recursive method, there is a corresponding iterative method. Let me try to solve it iteratively.

I cannot implement it without using another class to store multi-informaiton. Each time stack pops, I need to access lower bound, upper bound, and current TreeNode.

 /**  
  * Definition for binary tree  
  * public class TreeNode {  
  *   int val;  
  *   TreeNode left;  
  *   TreeNode right;  
  *   TreeNode(int x) { val = x; }  
  * }  
  */  
 public class Solution {  
   class Node{ // need another class to store multi information  
     int low, up; // means the TreeNode covers [low, up], low and up are all index  
     TreeNode t;  
     Node(int l, int p, TreeNode node){  
       low = l;  
       up = p;  
       t = node;  
     }  
   }  
   public TreeNode sortedArrayToBST(int[] num) {  
     if(num == null || num.length == 0) return null;  
     Stack<Node> stack = new Stack<Node>();  
     // initialize  
     TreeNode root = new TreeNode(num[(num.length-1)/2]);  
     Node rootNode = new Node(0,num.length-1,root);  
     stack.push(rootNode);  
     // iteration  
     while(!stack.isEmpty()){  
       Node node = stack.pop();  
       int middle = (node.low+node.up)/2; // cut half for [low, up]  
       // [low, middle-1]  
       if(middle-1 >= node.low){  
         TreeNode leftnode = new TreeNode(num[(middle-1+node.low)/2]);  
         node.t.left = leftnode;  
         Node left = new Node(node.low, middle-1, leftnode);  
         stack.push(left);  
       }  
       // [middle+1, up]  
       if(middle+1 <= node.up){  
         TreeNode rightnode = new TreeNode(num[(middle+1+node.up)/2]);  
         node.t.right = rightnode;  
         Node right = new Node(middle+1, node.up, rightnode);  
         stack.push(right);  
       }  
     }  
     return root;  
   }  
 }  

Recover Binary Search Tree

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?

Naive Way:O(1)的做法我实在是想不出来，明明inorder traversal 就要O(n) space了。

这是O(n) space 的做法，这样做比较无脑，任何错误都可以纠正。

 /**  
  * Definition for binary tree  
  * public class TreeNode {  
  *   int val;  
  *   TreeNode left;  
  *   TreeNode right;  
  *   TreeNode(int x) { val = x; }  
  * }  
  */  
 public class Solution {  
   public void recoverTree(TreeNode root) {  
     List<Integer> vals = new ArrayList<Integer>();  
     List<TreeNode> nodes = new ArrayList<TreeNode>();  
     inorder(root, nodes, vals);  
     Collections.sort(vals);  
     for(int i = 0;i < nodes.size();i++)  
       nodes.get(i).val = vals.get(i);  
   }  
   private void inorder(TreeNode root, List<TreeNode> nodes, List<Integer> vals){  
     if(root==null) return;  
     inorder(root.left, nodes, vals);  
     nodes.add(root);  
     vals.add(root.val);  
     inorder(root.right, nodes, vals);  
   }  
 }  

Improved Way: 原来还有一个叫Morris Threading Traversal 的东西。这里有一个blog，是一个中国人专门写Morris Traversal的，http://www.cnblogs.com/AnnieKim/archive/2013/06/15/morristraversal.html，非常有用。线索二叉树。

针对这道题，Morris Traversal 解决了用O(1)的space遍历BST，但是找到错误交换的两个点依然是一个问题。肯定是在Morris Traversal的算法上修改。先把Morris Traversal的算法列出来。

 /**  
  * Definition for binary tree  
  * public class TreeNode {  
  *   int val;  
  *   TreeNode left;  
  *   TreeNode right;  
  *   TreeNode(int x) { val = x; }  
  * }  
  */  
 public void morrisTraversal(TreeNode root){  
     TreeNode temp = null;  
     while(root!=null){  
       if(root.left!=null){  
         // connect threading for root  
         temp = root.left;  
         while(temp.right!=null && temp.right != root)  
           temp = temp.right;  
         // the threading already exists  
         if(temp.right!=null){  
           temp.right = null;  
           System.out.println(root.val);  
           root = root.right;  
         }else{  
           // construct the threading  
           temp.right = root;  
           root = root.left;  
         }  
       }else{  
         System.out.println(root.val);  
         root = root.right;  
       }  
     }  
   }   

两个加粗部分对应遍历时的输出顺序，所以找出错误交换的节点也应该是在这里修改。如何修改？因为MorrisTraversal得到的应该是升序的，所以前一个大于后一个说明前一个一定是错的，为什么不是后一个是错的呢？因为后一个比前一个小说明后一个应该被先遍历到，前一个节点至少应该是后一个节点那么大小。而一旦找到了第一个错误的节点，第二次再遇到前一个大于后一个的时候，错误的就是后一个了。为什么呢？因为我们知道了第一个错误的节点是value大于它本来的value，所以我们现在要找的就是value小于它本来value的节点，因为这个节点本来应该是第一个错误的节点所在的位置。
而当出错的是连续两个节点时，可能只检测到一个非升序情况，因为连着的这两个是错的。这时要暂时另第二个错误节点等于第一个后面的节点。

所以要做的就是把  
System.out.println(root.val);
替换成
if(pre!=null && pre.val > root.val){
      if(first==null){first = pre;second = root;}
      else{second = root;} 
}
pre = root;  

这里非常好理解，因为原来是按照System.out.println(root.val)的顺序输出的，也就是说该位置得到的每一次root值都是排好序的，那么将上一次的root作为这一次的pre就是按照顺序的pre和root，如果二者大小关系不对，可知错误节点在此处。

 public void recoverTree(TreeNode root) {  
     TreeNode pre = null;  
     TreeNode first = null, second = null;  
     // Morris Traversal  
     TreeNode temp = null;  
     while(root!=null){  
       if(root.left!=null){  
         // connect threading for root  
         temp = root.left;  
         while(temp.right!=null && temp.right != root)  
           temp = temp.right;  
         // the threading already exists  
         if(temp.right!=null){  
           if(pre!=null && pre.val > root.val){  
             if(first==null){first = pre;second = root;}  
             else{second = root;}  
           }  
           pre = root;  
           temp.right = null;  
           root = root.right;  
         }else{  
           // construct the threading  
           temp.right = root;  
           root = root.left;  
         }  
       }else{  
         if(pre!=null && pre.val > root.val){  
           if(first==null){first = pre;second = root;}  
           else{second = root;}  
         }  
         pre = root;  
         root = root.right;  
       }  
     }  
     // swap two node values;  
     if(first!= null && second != null){  
       int t = first.val;  
       first.val = second.val;  
       second.val = t;  
     }  
   }