Python inOrderTraversal O(n)


  • 0
    Y
    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        
        def recoverTree(self, root):
            """
            :type root: TreeNode
            :rtype: void Do not return anything, modify root in-place instead.
            """
            
            def inorderTraversal(node):
                if node is None:
                    return []
                
                return inorderTraversal(node.left) + [node] + inorderTraversal(node.right)
            
            def switch(n1, n2):
                n1.left, n1.right, n2.left, n2.right = n2.left, n2.right, n1.left, n1.right
                return
            
            q = inorderTraversal(root)
            pairs = []
            i = 0
            while i < len(q)-1:
                if q[i].val > q[i+1].val:
                    pairs.append(i)
                i += 1
            
            if len(pairs) == 1:
                i = pairs[0]
                n1, n2 = q[i], q[i+1]
            elif len(pairs) == 2:
                i, j = pairs
                n1, n2 = q[i], q[j+1]
            n1.val, n2.val = n2.val, n1.val
                
            return
    

    Inorder Traversal, find the incorrect pairs. Switch the values. Done


Log in to reply
 

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