Construct Binary Tree from Preorder and Inorder
LeetCode 105 前序与中序构造二叉树：用哈希表加速定位根。
#resource / algorithm
#type / howto
#status / evergreen
#ds / tree
#algo / recursion
#source / leetcode
[!info] related notes 算法面试题型 MOC 二叉树高频题
Construct Binary Tree from Preorder and Inorder
LeetCode: https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
思路
- 前序遍历：第一个元素一定是当前子树的根。
- 中序遍历：根把序列切成左子树与右子树。
- 用
inorderMap[val] = index在 O(1) 时间找到根在中序的位置。
递归函数常用参数：
preStart, preEnd：当前子树在 preorder 的区间inStart, inEnd：当前子树在 inorder 的区间
代码（JavaScript）
var buildTree = function(preorder, inorder) {
const inorderMap = new Map();
for (let i = 0; i < inorder.length; i++) inorderMap.set(inorder[i], i);
const build = (preStart, preEnd, inStart, inEnd) => {
if (preStart > preEnd || inStart > inEnd) return null;
const rootVal = preorder[preStart];
const root = new TreeNode(rootVal);
const rootIndex = inorderMap.get(rootVal);
const leftSize = rootIndex - inStart;
root.left = build(preStart + 1, preStart + leftSize, inStart, rootIndex - 1);
root.right = build(preStart + leftSize + 1, preEnd, rootIndex + 1, inEnd);
return root;
};
return build(0, preorder.length - 1, 0, inorder.length - 1);
};