题目描述输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8} 和中序遍历序列{4,7,2,1,5,3,8,6} ,则重建二叉树并返回。 解法 1: 递归首先前序/后序遍历 + 中序遍历可以重建二叉树。题目考察的就是前序+中序来重建二叉树,后序+中序的思路是类似的。 例子与思路假设有二叉树如下: 1
/ 2 3
/ 4 5
它的前序遍历的顺序是:1 2 4 5 3 。中序遍历的顺序是:4 2 5 1 3 因为前序遍历的第一个元素就是当前二叉树的根节点。那么,这个值就可以将中序遍历分成 2 个部分。在以上面的例子,中序遍历就被分成了 4 2 5 和 3 两个部分。4 2 5 就是左子树,3 就是右子树。 最后,根据左右子树,继续递归即可。 专注前端与算法的系列干货分享,欢迎关注(¬‿¬): 「微信公众号:心谭博客」| | GitHub 代码实现// ac地址:https://www./practice/8a19cbe657394eeaac2f6ea9b0f6fcf6
// 原文地址:https:///2019-12-21-re-construct-btree/
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
/**
* @param {TreeNode} pre
* @param {TreeNode} vin
* @return {TreeNode}
*/
function reConstructBinaryTree(pre, vin) {
if (!pre.length || !vin.length) {
return null;
}
const rootVal = pre[0];
const node = new TreeNode(rootVal);
let i = 0; // i有两个含义,一个是根节点在中序遍历结果中的下标,另一个是当前左子树的节点个数
for (; i < vin.length; ++i) {
if (vin[i] === rootVal) {
break;
}
}
node.left = reConstructBinaryTree(pre.slice(1, i + 1), vin.slice(0, i));
node.right = reConstructBinaryTree(pre.slice(i + 1), vin.slice(i + 1));
return node;
}
|