题解 | #重建二叉树#
重建二叉树
http://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6
思路：先序遍历列表的第一个节点一定是二叉树的根节点，也是中序遍历列表中划分左右子树的关键。
在中序遍历列表中找到先序遍历列表中第一个节点，以此为界限可以将二叉树分为左右子树，可以得知左子树和右子树的长度，在先序遍历列表中划分出来。再依次拿出先序遍历列表中的第一个节点构成左/右子树的根节点，直到传入的先序序列或中序序列为空结束遍历，返回根节点。
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function reConstructBinaryTree(pre, vin)
{
if(!pre.length||!vin.length){
return null
}
let root = pre[0]
let tnode = new TreeNode(root)
let index = vin.indexOf(root)
tnode.left = reConstructBinaryTree(pre.slice(1,index+1),vin.slice(0,index))
tnode.right = reConstructBinaryTree(pre.slice(index+1),vin.slice(index+1))
return tnode
}
module.exports = {
reConstructBinaryTree : reConstructBinaryTree
};
查看16道真题和解析
