HHot 100C++ 图解

105. 从前序与中序遍历序列构造二叉树

中等 二叉树 在力扣上做

一句话套路前序定根 + 中序切两半(下标哈希加速)

题目描述

给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。

 

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

 

提示:

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • preorder 和 inorder 均 无重复 元素
  • inorder 均出现在 preorder
  • preorder 保证 为二叉树的前序遍历序列
  • inorder 保证 为二叉树的中序遍历序列

思路

时间O(n)
空间O(n)

思路

pre[pl] 一定是当前子树的根;在 inorder 里查到它的位置 k,[inL, k) 是左子树、(k, inR] 是右子树,左子树结点数 = k - inL,据此切分 preorder 区间递归。用哈希表存「值 -> 中序下标」把查找降到 O(1)。

易错

右子树的 preorder 起点是 pl + (k - inL) + 1,不是 pl + 1。

前提

结点值互不相同(题目保证),否则无法唯一定位。

对照

Q106(中序+后序)对称 —— 后序的根在数组末尾。

图解

3 0 9 1 20 2 15 3 7 4
数组(来自本仓库测试数据,下标从 0 开始)

C++17 题解

src/08_binary_tree.cpp24 行
namespace lc0105 {
class Solution {
 public:
  TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    for (int i = 0; i < (int)inorder.size(); ++i) pos_[inorder[i]] = i;
    return build(preorder, 0, (int)preorder.size() - 1, inorder, 0, (int)inorder.size() - 1);
  }

 private:
  unordered_map<int, int> pos_;  // 值 -> 中序下标

  TreeNode* build(const vector<int>& pre, int pl, int pr, const vector<int>& in, int il,
                  int ir) {
    if (pl > pr) return nullptr;
    int rootVal = pre[pl];
    int k = pos_[rootVal];            // 根在中序里的位置
    int leftSize = k - il;            // 左子树结点个数
    TreeNode* root = new TreeNode(rootVal);
    root->left = build(pre, pl + 1, pl + leftSize, in, il, k - 1);
    root->right = build(pre, pl + leftSize + 1, pr, in, k + 1, ir);
    return root;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q105_build_from_pre_in11 行
lc0105::Solution s;
vector<int> pre{3, 9, 20, 15, 7};
vector<int> in{9, 3, 15, 20, 7};
TreeNode* t = s.buildTree(pre, in);
CHECK_EQ(treeToVec(t), OptVec{3, 9, 20, nullopt, nullopt, 15, 7});
freeTree(t);
vector<int> pre2{-1};
vector<int> in2{-1};
TreeNode* u = s.buildTree(pre2, in2);
CHECK_EQ(treeToVec(u), OptVec{-1});
freeTree(u);

↑↓ 选择↵ 打开/ 随时唤起