Share my recursive and iterative Python solutions, O(N) ~70 ms


  • 1
    D

    Both solutions use dictionary to create mapping between value and index of in-order traversal.

    Recursive one: use deque for efficient popleft()

    from collections import deque
    class Solution:
        # @param {integer[]} preorder
        # @param {integer[]} inorder
        # @return {TreeNode}
        def buildTree(self, preorder, inorder):
            def _buildTreeHelper(preorder, inorder, start, end, inorderMapping):
                # escape condition
                if start > end:
                    return None
    
                # root is the first one in pre-order
                root = TreeNode(preorder.popleft())
                # get root's index in in-order
                index = inorderMapping[root.val]
                # build left / right sub-trees
                root.left = _buildTreeHelper(preorder, inorder, start, index-1, inorderMapping)
                root.right = _buildTreeHelper(preorder, inorder, index+1, end, inorderMapping)
                return root
    
            # generate mapping from value to index
            inorderMapping = {inorder[index] : index for index in range(len(inorder))}
            preorder = deque(preorder)
            return _buildTreeHelper(preorder, inorder, 0, len(inorder)-1, inorderMapping)
    

    Iterative one: I could use deque too. Instead, I just reverse inorder and use pop() instead of pop(0)
    Use stack to store start / end index of inorder, as well as parent and indicator of left child or right child.

    class Solution:
        # @param {integer[]} preorder
        # @param {integer[]} inorder
        # @return {TreeNode}
        def buildTree(self, preorder, inorder):
            dummy = TreeNode(0)
            if inorder:
                # generate mapping from value to index
                inorderMapping = {inorder[index] : index for index in range(len(inorder))}
                preorder = preorder[::-1]
                stack = [(0, len(inorder)-1, dummy, True)]
                while stack:
                    start, end, parent, left = stack.pop()
                    node = TreeNode(preorder.pop())
                    if left:
                        parent.left = node
                    else:
                        parent.right = node
                    index = inorderMapping[node.val]
                    if index < end:
                        stack.append((index+1, end, node, False))
                    if index > start:
                        stack.append((start, index-1, node, True))
    
            return dummy.left

Log in to reply
 

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