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