从中序与后序遍历序列构造二叉树

题目描述：

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗二叉树。

示例 1：

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7] 

示例 2：

输入： inorder = [-1], postorder = [-1]
输出： [-1]

链接：

解题思路

二叉树中序遍历的顺序为：

• 先递归地遍历左子树；
• 随后遍历根节点；
• 最后递归地遍历右子树。

二叉树后序遍历的顺序为：

• 先递归地遍历左子树；
• 随后递归地遍历右子树；
• 最后遍历根节点。

思路一：递归

对于任意一颗树而言，

中序遍历的形式总是 [ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]

后序遍历的形式总是[ [左子树的前序遍历结果], [右子树的前序遍历结果]，根节点 ]

即根节点总是后序遍历中的最后一个节点。

• 创建哈希表来存储中序序列，即建立一个（元素，下标）键值对的哈希表（为了高效查找根节点元素在中序遍历数组中的下标）
• 定义递归函数 helper(in_left, in_right) 表示当前递归到中序序列中当前子树的左右边界，递归入口为helper(0, n – 1)

利用哈希表 O(1) 查询当根节点在中序遍历中下标为 index。从 in_left 到 index – 1 属于左子树，从 index + 1 到 in_right 属于右子树

根据后序遍历逻辑，递归创建右子树 helper(index + 1, in_right) 和左子树 helper(in_left, index – 1)。注意这里有需要先创建右子树，再创建左子树的依赖关系。可以理解为在后序遍历的数组中整个数组是先存储左子树的节点，再存储右子树的节点，最后存储根节点，如果按每次选择「后序遍历的最后一个节点」为根节点，则先被构造出来的应该为右子树

/**
 * @param {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
var buildTree = function(inorder, postorder) {
  // 从后序遍历的最后一个元素开始
  let post_idx = postorder.length - 1;
  // 建立（元素，下标）键值对的哈希表
  const idx_map = new Map();
  inorder.forEach((val, idx) => {
    idx_map.set(val, idx);
  });
  const helper = (in_left, in_right) => {
    // 如果这里没有节点构造二叉树了，就结束
    if (in_left > in_right) {
        return null;
    }
    // 选择 post_idx 位置的元素作为当前子树根节点
    const root_val = postorder[post_idx];
    const root = new TreeNode(root_val);
    // 根据 root 所在位置分成左右两棵子树
    const index = idx_map.get(root_val);
    // 下标减一
    post_idx--;
    // 构造右子树
    root.right = helper(index + 1, in_right);
    // 构造左子树
    root.left = helper(in_left, index - 1);
    return root;
  }
  return helper(0, inorder.length - 1);
};

时间复杂度： O(n), 其中 n 是二叉树的节点数

空间复杂度： O(n)，存储哈希表

参考资料

106. 从中序与后序遍历序列构造二叉树