原题链接：https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
image.png
解题思路：
-
递归： ，根据后序遍历的特性，后序list的末位即为根节点，并在中序list中寻找该节点，左边
[9]即为根节点的左子树，右边[15,20,7]即为根节点的左子树， 因此维护一个词典，存储中序遍历的val->idx。
Python3代码：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
def helper(left, right):
# 没有节点构造二叉树了，就结束
if left>right:
return None
# 后序遍历的末节点为根节点
val = postorder.pop()
root = TreeNode(val)
# 构造右子树
root.right = helper(idx_map[val]+1, right)
# 构造左子树
root.left = helper(left, idx_map[val]-1)
return root
idx_map = {val:idx for idx, val in enumerate(inorder)}
return helper(0, len(postorder)-1)
