Super simple python solution with clear explain


  • 0
    0

    Here you go:

    '''
    use the feature "inorder print sorted", so you can see two cases
    
    1 2 7 4 5 6 3 8 9
        p c   p c
        1st   2nd  
        
    or
    
    1 2 4 3 5 6
        p c   
        1st   
    
    if one error, swap( 1st prev, 1st current node ) 
    if two error, swap( 1st prev, 2nd current node )
        
    '''
    import sys
    
    class Solution(object):
        def __init__(self):
            self.prev = TreeNode(-sys.maxint)
            
        def recoverTree(self, root):
            two = []
            self.dfs(root, two)
            two[0].val, two[1].val = two[1].val, two[0].val
        
        def dfs(self, node, two):
            if not node:
                return 
            self.dfs(node.left, two)
            
            if not two and self.prev.val > node.val:    
                two.append(self.prev)
                two.append(node)
            elif self.prev.val > node.val:    
                two[1] = node
            self.prev = node
            
            self.dfs(node.right, two)
            return 
    

Log in to reply
 

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