首页>itarticle>105. construct binary tree from preorder and inorder traversal
105. construct binary tree from preorder and inorder traversal
admin11月 12, 20200
# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, x):# self.val = x# self.left = None# self.right = NoneclassSolution(object):defbuildTree(self,preorder,inorder):""" :type preorder: List[int] :type inorder: List[int] :rtype: TreeNode """# inorder:DBHEIAFCG# preorder:ABDEHICFGifnotinorder:# inorder base is [], not [] return True, [] == None return False.returnNoneroot=TreeNode(preorder[0])pos=inorder.index(preorder[0])# find the middle position, left part and right partroot.left=self.buildTree(preorder[1:1+pos],inorder[:pos])# numbers of inorder and preorder are sameroot.right=self.buildTree(preorder[pos+1:],inorder[pos+1:])returnroot
近期评论