Python Inorder Traversal Solution


  • 1
    H

    Inorder Traversal will get a sorted list, from the end to start, add the right value to each element, then rebuild the BST

    class Solution(object):
        def convertBST(self, root):
            """
            :type root: TreeNode
            :rtype: TreeNode
            """
            node=[]
            ids=[0]
            if not root : return None
            
            def inorder(root):
                if not root : return
                inorder(root.left)
                node.append(root.val)
                inorder(root.right)
    
            def inorder2(root):
                if not root : return
                inorder2(root.left)
                root.val=node[ids[0]]
                ids[0]+=1
                inorder2(root.right)
            
            inorder(root)
            
            n =len(node)
            for i in range(n-2,-1,-1):
                node[i]+=node[i+1]
            print node    
            inorder2(root )
    
            return root
    

Log in to reply
 

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