106. Construct Binary Tree from Inorder and Postorder Traversal
106. Construct Binary Tree from Inorder and Postorder Traversal
🟠 🔖 树
数组
哈希表
分治
二叉树
🔗 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:
![](https://assets.leetcode.com/uploads/2021/02/19/tree.jpg)
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 题 类似。
构造二叉树,第一件事一定是找根节点,然后想办法构造左右子树。
后序遍历结果最后一个值就是根节点的值,然后再根据中序遍历结果确定左右子树的节点。
不断的递归直到所有的树都生成完成。
![](/leetcode-js/assets/106-CkwIJTG_.png)
递归时直接传入需要的 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;
};