重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。Leetcode 剑指 offer 07
javascript
const buildTree = (preorder, inorder) => {
// 使用 map 存放中序遍历，key 为每个值的下标
let rootMap = new Map();
for (let i = 0; i < inorder.length; i++) {
rootMap.set(inorder[i], i);
}
//递归函数的三个参数分别对应：先序中根节点位置，中序中的左边界，中序中的右边界
const fn = (root, left, right) => {
// 左右边界会逐渐向中间靠拢，所以当左边界超出右边界，说明已经完成
if (left > right) return null;
// 从先序中获取当前根节点
let node = new TreeNode(preorder[root]);
// 拿到当前根节点在中序遍历中的位置
let site = rootMap.get(preorder[root]);
// 递归左子树
node.left = fn(root + 1, left, site - 1);
// 递归右子树，根节点位置：root + 左子树节点数量 + 1
node.right = fn(root + (site - left) + 1, site + 1, right);
// 返回拼接好的树节点
return node;
};
return fn(0, 0, inorder.length - 1);
};const buildTree = (preorder, inorder) => {
// 使用 map 存放中序遍历，key 为每个值的下标
let rootMap = new Map();
for (let i = 0; i < inorder.length; i++) {
rootMap.set(inorder[i], i);
}
//递归函数的三个参数分别对应：先序中根节点位置，中序中的左边界，中序中的右边界
const fn = (root, left, right) => {
// 左右边界会逐渐向中间靠拢，所以当左边界超出右边界，说明已经完成
if (left > right) return null;
// 从先序中获取当前根节点
let node = new TreeNode(preorder[root]);
// 拿到当前根节点在中序遍历中的位置
let site = rootMap.get(preorder[root]);
// 递归左子树
node.left = fn(root + 1, left, site - 1);
// 递归右子树，根节点位置：root + 左子树节点数量 + 1
node.right = fn(root + (site - left) + 1, site + 1, right);
// 返回拼接好的树节点
return node;
};
return fn(0, 0, inorder.length - 1);
};
