105. Construct Binary Tree from Preorder and Inorder Traversal
105. Construct Binary Tree from Preorder and Inorder Traversal
🟠 🔖 树
数组
哈希表
分治
二叉树
🔗 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:
![](https://assets.leetcode.com/uploads/2021/02/19/tree.jpg)
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.
题目大意
根据一棵树的前序遍历与中序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
解题思路
构造二叉树,第一件事一定是找根节点,然后想办法构造左右子树。
前序遍历结果第一个就是根节点的值,然后再根据中序遍历结果确定左右子树的节点。
不断的递归直到所有的树都生成完成。
![](/leetcode-js/assets/2-6-10-mUIiVbyR.png)
递归时直接传入需要的 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;
};