Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
For example, given
inorder = [9,3,15,20,7] postorder = [9,15,7,20,3]
Return the following binary tree:
3
/ 9 20
/ 15 7
我们发现在后序遍历中pop出来的结果是整个树的节点 比如 3， 20 然后找出这个节点在先序排列数组里面的位置 那么此位置的左边就是此节点的左子树 右边就是她的右子树.
步骤：
1. 从后序遍历里面 pop一个元素
2. 在先序遍历里面找到这个元素的位置 并且把他当做一个节点
3. 那么这个节点的左边就是左子树 右边就是右子树
1 # Definition for a binary tree node. 2 # class TreeNode: 3 # def __init__(self, x): 4 # self.val = x 5 # self.left = None 6 # self.right = None 7 8 class Solution: 9 def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode: 10 def helper(in_left, in_right): 11 # if there is no elements to construct subtrees 12 if in_left > in_right: 13 return None 14 15 # pick up the last element as a root 16 val = postorder.pop() 17 root = TreeNode(val) 18 19 # root splits inorder list 20 # into left and right subtrees 21 index = idx_map[val] 22 23 # build right subtree 24 root.right = helper(index + 1, in_right) 25 # build left subtree 26 root.left = helper(in_left, index - 1) 27 return root 28 29 # build a hashmap value -> its index 30 idx_map = {val:idx for idx, val in enumerate(inorder)} 31 return helper(0, len(inorder) - 1)
吐槽： 用c做真的很难啊 还得自己做哈希表。。。。高级语言真的香
原文：https://www.cnblogs.com/shwzh1990/p/12784238.html