My AC Python code

  • 0

    It is not hard as long as you are familiar with the feature of preorder and inorder traversal.

    # 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 buildTree(self, preorder, inorder):
            :type preorder: List[int]
            :type inorder: List[int]
            :rtype: TreeNode
            def construct(preorder, x1, y1, inorder, x2, y2):
                if y1-x1 == 0:  return None
                root = TreeNode(preorder[x1])
                # find the root in inorder
                i = x2
                while i < y2:
                    if inorder[i] == preorder[x1]:  break
                    i += 1
                # partition left subtree and right subtree
                root.left = construct(preorder, x1+1, x1+1+(i-x2), inorder, x2, i)
                root.right = construct(preorder, x1+1+(i-x2), y1, inorder, i+1, y2)
                return root
            return construct(preorder, 0, len(preorder), inorder, 0, len(inorder))

Log in to reply

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