105. 从前序与中序遍历序列构造二叉树
105. 从前序与中序遍历序列构造二叉树
🟠 🔖 树
数组
哈希表
分治
二叉树
🔗 力扣
LeetCode
题目
Given two integer arrays preorder
and inorder
where preorder
is the preorder traversal of a binary tree and inorder
is the inorder traversal of the same tree, construct and return the binary tree.
Example 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
Example 2:
Input: preorder = [-1], inorder = [-1]
Output: [-1]
Constraints:
1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder
andinorder
consist of unique values.- Each value of
inorder
also appears inpreorder
. preorder
is guaranteed to be the preorder traversal of the tree.inorder
is guaranteed to be the inorder traversal of the tree.
题目大意
根据一棵树的前序遍历与中序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
解题思路
构造二叉树,第一件事一定是找根节点,然后想办法构造左右子树。
前序遍历结果第一个就是根节点的值,然后再根据中序遍历结果确定左右子树的节点。
不断的递归直到所有的树都生成完成。
递归时直接传入需要的 slice 范围作为输入, 可以避免申请对应 inorder 索引的内存。
代码
/**
* @param {number[]} preorder
* @param {number[]} inorder
* @return {TreeNode}
*/
var buildTree = function (preorder, inorder) {
if (preorder.length == 0) return null;
let root = new TreeNode(preorder[0]);
for (let i = 0; i < preorder.length; i++) {
if (inorder[i] === root.val) {
root.left = buildTree(preorder.slice(1, i + 1), inorder.slice(0, i));
root.right = buildTree(preorder.slice(i + 1), inorder.slice(i + 1));
break;
}
}
return root;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
106 | 从中序与后序遍历序列构造二叉树 | [✓] | 树 数组 哈希表 2+ |