My Python solution using a stack


  • 0
    Z
    class Solution(object):
        def buildTree(self, preorder, inorder):
            """
            :type preorder: List[int]
            :type inorder: List[int]
            :rtype: TreeNode
            """
            if len(preorder) == 0:
                return None
            root = TreeNode(preorder.pop(0))
            stack = [(root,'right'),(root,'left')]
            while len(preorder) > 0:
                element = preorder.pop(0)
                while len(stack) > 0:
                    last = stack.pop()
                    if last[1] == 'left':
                        if inorder.index(element) < inorder.index(last[0].val):
                            newNode = TreeNode(element)
                            last[0].left = newNode
                            stack.append((newNode,'right'))
                            stack.append((newNode,'left'))
                            break
                    else:
                        if len(stack) <= 0:
                            newNode = TreeNode(element)
                            last[0].right = newNode
                            stack.append((newNode,'right'))
                            stack.append((newNode,'left'))     
                            break
                        else:
                            second_last = stack[-1]
                            if inorder.index(element) < inorder.index(second_last[0].val):
                                newNode = TreeNode(element)
                                last[0].right = newNode
                                stack.append((newNode,'right'))
                                stack.append((newNode,'left'))
                                break
            return root

Log in to reply
 

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