【剑指 Offer】07. 重建二叉树
Opened this issue · 1 comments
sayid760 commented
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
/*
1)前序的第一个是树的顶点,用这个顶点在中序找出对应的左边和右边
2)找到中序的对应左边右边后,递归构建左边树和右边树
3)返回整棵树
*/
var buildTree = function (preorder, inorder) {
if(!preorder.length || !inorder.length) return null
const rootVal = preorder[0];
const node = new TreeNode(rootVal);
let i = 0; // i有两个含义,一个是根节点在中序遍历结果中的下标,另一个是当前左子树的节点个数
for (; i < inorder.length; ++i) {
if (inorder[i] === rootVal) { // 说明找到中序了
break;
}
}
// slice(从什么开始,到什么结束且不包括结束位置) 前序的1位置(下标0已经是根节点) , 中序的左侧位置
node.left = buildTree(preorder.slice(1, i + 1), inorder.slice(0, i));
node.right = buildTree(preorder.slice(i + 1), inorder.slice(i + 1));
return node;
};
let preorder = [3, 9, 20, 15, 7]
let inorder = [9, 3, 15, 20, 7]
console.log(buildTree(preorder, inorder))