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 <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000preorder和inorder均 无重复 元素inorder均出现在preorderpreorder保证 为二叉树的前序遍历序列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(中序+后序)对称 —— 后序的根在数组末尾。
图解
数组(来自本仓库测试数据,下标从 0 开始)
C++17 题解
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;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
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);