题目

根据一棵树的中序遍历与后序遍历构造二叉树。
image.png

思路

中序遍历：每次遍历左孩子，再遍历根节点，最后遍历右孩子。
后序遍历：每次

后序遍历最后一个元素为根节点root；
由根节点root可以将中序遍历分为树的left、right。
由此可知，使用递归方法。

image.png

为了避免每次花费时间查找inorder数组中的索引，使用一个hash表提前存储所有节点在inorder数组中的索引，用空间换取时间。

  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
  8. class Solution:
  9.     def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
  10.         root_index = {val : idx for idx, val in enumerate(inorder)}
  11.         def helper(left, right):
  12.             # 当左边界 > 右边界，无法构造左右子树，结束
  13.             if left > right:
  14.                 return None
  16.             val = postorder.pop() # 后序遍历最后一个元素为当前子树的根节点的值
  17.             root = TreeNode(val) # 初始化节点
  18.             idx = root_index[val] # 找到val在中序遍历中的位置
  20.             # 根据root，将中序遍历分为左子树、右子树
  21.             # root.left = helper(left, idx - 1)
  22.             root.right = helper(idx + 1, right)
  23.             root.left = helper(left, idx - 1)
  25.             return root  
  27.         return helper(0, len(inorder) - 1) # 中序遍历的左边界0和右边界len(inorder) - 1

有坑？
如果先构建左子树，代码就不对了。

因为根节点是通过后序排列的back确定的，后序的顺序是left(a) right(b) root(c)，所以下一次的back(b)应该是属于root的右子树的

https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/solution/shou-hua-tu-jie-cong-zhong-xu-yu-hou-xu-bian-li-xu/