根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution(object):
def buildTree(self, inorder, postorder):
"""
:type inorder: List[int]
:type postorder: List[int]
:rtype: TreeNode
"""
if not postorder:
return None
if len(postorder) == 1:
return TreeNode(postorder[0])
t = postorder.pop()
t_idx = inorder.index(t)
inorderLeft = inorder[:t_idx]
inorderRight = inorder[t_idx+1:]
postorderLeft = postorder[:len(inorderLeft)]
postorderRight = postorder[len(inorderLeft):]
root = TreeNode(t)
root.left = self.buildTree(inorderLeft, postorderLeft)
root.right = self.buildTree(inorderRight, postorderRight)
return root
|
