跳到主要内容

从中序与后序遍历序列构造二叉树

题目链接

https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

题目

给定两个整数数组 inorderpostorder ,其中 inorder 是二叉树的中序遍历,postorder 是同一棵树的后序遍历,请构造二叉树并返回其根节点。

示例 1:

输入: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: inorder = [-1], postorder = [-1]
输出: [-1]

提示:

  • 1 <= inorder.length <= 3000
  • postorder.length == inorder.length
  • -3000 <= inorder[i], postorder[i] <= 3000
  • inorderpostorder 均无重复元素
  • postorderinorder 均出现在 preorder
  • inorder 保证为二叉树的中序遍历序列
  • postorder 保证为二叉树的后序遍历序列

思路

题目要求根据中序和后序遍历序列构造二叉树。后序遍历的特点是最后一个元素为根节点,而中序遍历的特点是根节点左边的元素构成左子树,右边的元素构成右子树。因此,我们可以利用递归的方法来构造二叉树:

  1. 根据后序遍历的最后一个元素确定根节点。
  2. 在中序遍历中找到根节点的位置,从而确定左子树和右子树。
  3. 递归构造左子树和右子树。

通过递归地将中序和后序遍历序列划分为左右子树的序列,最终可以构造出完整的二叉树。

代码

/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {number[]} inorder
* @param {number[]} postorder
* @return {TreeNode}
*/
var buildTree = function(inorder, postorder) {
if(inorder.length === 0) {
return null
}
const root = new TreeNode(postorder.pop())
const index = inorder.indexOf(root.val)
root.right = buildTree(inorder.slice(index + 1), postorder)
root.left = buildTree(inorder.slice(0, index), postorder)

return root
};

复杂度分析

  • 时间复杂度:O(n2)O(n^2),其中 nn 是数组的长度。在每次递归调用中,我们需要使用 indexOf 函数找到中序遍历中根节点的位置,最坏情况下,这个查找过程是 O(n)O(n)
  • 空间复杂度:O(n)O(n),递归栈的空间消耗取决于树的高度,最坏情况下需要 O(n)O(n) 的栈空间。