106 construct binary tree from inorder and postorder traversal
106. Construct Binary Tree from Inorder and Postorder Traversal
题目： https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
难度 : Medium
inorder 是 左 -> 根 -> 右 postorder 是 左 -> 右 -> 根
跟105基本一样
还是先弄了一个递归可用版本
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
照抄105
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)
