問題描述
Given preorder and inorder traversal of a tree, construct the binary tree.
思路
- 用recursive的方法愈腾，從上往下append child nodes，分左右recur旭等；
- 通過對比preorder和inorder扼仲，得出每個 子root 和他的左右兩棵樹耘子；
每次return head（即 子root过咬，新建的Node）
當?shù)竭_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
