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

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

🎯 问题描述（来源于LeetCode）

描述：
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
说明：

• 1 <= inorder.length <= 3000

• postorder.length == inorder.length

• -3000 <= inorder[i], postorder[i] <= 3000

• inorder 和 postorder 都由 不同 的值组成

• postorder 中每一个值都在 inorder 中

• 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：递归+分治

思路1：代码实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        def createTree(inorder,postorder, n):
            if n == 0:
                return None  
            idx=inorder.index(postorder[n-1])
            node = TreeNode(inorder[idx])
            node.right = createTree(inorder[idx+1:n],postorder[idx:n-1],n-idx-1)
            node.left = createTree(inorder[0:idx], postorder[0:idx],idx)
            return node
        return createTree(inorder,postorder,len(inorder)) 

思路1：📊 性能分析

提交结果

• 运行时间：99ms击败35.63%
• 内存消耗：89.03MB击败36.50%

复杂度验证

• 时间复杂度：$O(N^2)$
• 空间复杂度：$O(N^2)$