问题描述
Given preorder and inorder traversal of a tree, construct the binary tree.
思路
- 用recursive的方法,从上往下append child nodes,分左右recur;
- 通过对比preorder和inorder,得出每个 子root 和他的左右两棵树;
每次return head(即 子root,新建的Node)
当到达leaf时,leaf也是子root,只不过此时preorder的长度不符合recur条件,直接return None,形成base case
def buildTree(self,preorder, inorder):
"""
:param preorder: List[int]
:param inorder: List[int]
:return: TreeNode
"""
if not preorder or not inorder:
return
head = None
if len(preorder) > 0:
index = inorder.index(preorder[0])
head = TreeNode(preorder[0])
head.left = self.buildTree(preorder[1:index+1], inorder[:index])
head.right = self.buildTree(preorder[index+1:], inorder[index+1:])
return head
网友评论