2014年4月22日 星期二

[LeetCode] Recover Binary Search Tree

Problem:
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:O(n)
public class Solution {
    public void recoverTree(TreeNode root) {
        if(root == null)
            return;
            
        Dao dao = new Dao();
        doInorder(root, dao);
        int val = dao.node1.val;
        dao.node1.val = dao.node2.val;
        dao.node2.val = val;
    }
 class Dao{
  TreeNode node1;
  TreeNode node2;
  TreeNode preroot;
 }
    
    public void doInorder(TreeNode root,Dao dao){
        if(root == null)
            return ;
        doInorder(root.left,dao); 
        if(dao.preroot == null)
         dao.preroot = root;
        else{
            if(dao.preroot.val > root.val){
                if(dao.node1 == null)
                 dao.node1 = dao.preroot;
                dao.node2 = root;    
            }
            dao.preroot = root;
        }    
        doInorder(root.right,dao);
    }
}
Key Concept: Use dao to store two wrong node, finally swap

沒有留言:

張貼留言