# 106 construct binary tree from inorder and postorder traversal

### 106. Construct Binary Tree from Inorder and Postorder Traversal

inorder 是 左 -> 根 -> 右 postorder 是 左 -> 右 -> 根

def buildTree(inorder, postorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
if postorder == inorder == []:
return None
else:
rootVal = postorder[-1]
root = TreeNode(rootVal)
k = inorder.index(rootVal)
root.left = buildTree(inorder[:k],postorder[:k])
root.right = buildTree(inorder[k+1:],postorder[k:-1])
return root



class Solution(object):
def buildTree(self, inorder, postorder):
"""
:type inorder: List[int]
:type postorder: List[int]
:rtype: TreeNode
"""
def buildTree(inorder, postorder, li, ri ,lp, rp ):
if lp > rp or li > ri:
return None

root = TreeNode(postorder[rp])
k = inorder.index(postorder[rp])

# left node
left = buildTree(inorder, postorder, li, k-1, lp, lp + k - li - 1)
right = buildTree(inorder, postorder, k+1, ri, lp+k-li, rp-1)

root.left = left
root.right = right

return root

return buildTree(inorder, postorder, 0, len(inorder) - 1, 0, len(postorder) - 1)



apachecn/AiLearning