根据一棵树的前序遍历与中序遍历构造二叉树
注意:
你可以假设树中没有重复的元素。
例如,给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树:
3
/
9 20
/
15 7
递归
/**
* @param {number[]} preorder
* @param {number[]} inorder
* @return {TreeNode}
*/
var buildTree = function (preorder, inorder) {
if (preorder.length !== inorder.length) {
return null;
}
const map = {};
for (let i = 0; i < inorder.length; i++) {
map[inorder[i]] = i;
}
return buildSubtree(preorder, inorder, 0, preorder.length - 1, map)
};
/**
* @param: preorder
* @param: inorder
* @param: start `中序遍历`的左子树开始位置
* @param: end `中序遍历`的右子树结束位置
* @param: map
*/
var buildSubtree = function (preorder, inorder, start, end, map) {
// start === end 时为叶子节点,
// start > end 表示 null
if (start > end) {
return null;
}
let val = preorder.shift();
// 前序遍历找出根节点
let root = new TreeNode(val);
// 中序遍历对应的根节点
let index = map[val];
// 递归全部左子树
root.left = buildSubtree(preorder, inorder, start, index - 1, map);
// 递归全部左子树
root.right = buildSubtree(preorder, inorder, index + 1, end, map);
return root;
};