An easy solution , python.


  • 0
    L

    This solution is easy to understand.
    for example, if the root travel result is [6,3,4,5,2], then we need to swap to 6,5,4,3,2. then reassign all node to the correct value.

    class Solution:
    # @param root, a tree node
    # @return a tree node
    def recoverTree(self, root):
        def travel(node,cache):            
            if(node==None):return;
            travel(node.left,cache);
            cache.append(node);
            travel(node.right,cache);
    
        if(root==None):return None;
        else:
            cache=[];
            travel(root,cache);
            
            vals= map(lambda x:x.val,cache);
            vals=sorted(vals);
    
            for i in range(len(cache)):
                cache[i].val=vals[i];
    
            return root;
    
    def recoverTree2(self, root):
        def travel(node,cache):            
            if(node==None):return;
            travel(node.left,cache);
            cache.append(node);
            travel(node.right,cache);
    
        if(root==None):return None;
        else:
            cache=[];
            travel(root,cache);
            
            i,j=0,len(cache)-1;
            
            k=i;
            while(k<j):
                if(cache[k].val> cache[k+1].val):
                    i=k;
                    break;
                k+=1;
    
            k=j;
            while(k>i):
                if(cache[k-1].val>cache[k].val):
                    j=k;
                    break;
                k-=1;
            cache[i].val,cache[j].val=cache[j].val,cache[i].val
    
            return root;

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.