2015年10月2日星期五

Leetcode 99 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?
Solution 1: in order traversal, use stack though, but at the end stack is empty. Below is iterative way, recursive is simpler but use system stack, same thing. A real O(1) need Morris Traversal.
 public class Solution {  
   public void recoverTree(TreeNode root) {  
     Deque<TreeNode> stack=new LinkedList<>();  
     TreeNode p1=null, p2=null, pre=null, x=root;  
     while (x!=null || !stack.isEmpty()) {  
       if (x!=null) {  
         stack.push(x);  
         x=x.left;  
       }  
       else {  
         x=stack.pop();  
         if (pre!=null && pre.val>x.val) {  
           if (p1==null) {  
             p1=pre;  
             p2=x;// incase in sorted array p1,p2 is next to each other  
           }  
           else p2=x;  
         }  
         pre=x;  
         x=x.right;  
       }  
     }  
     int temp=p1.val;  
     p1.val=p2.val;  
     p2.val=temp;  
   }  
 }  

没有评论:

发表评论