LeetCode 106. Construct Binary Tree from Inorder and Postorder Traversal 题解

LeetCode 106. Construct Binary Tree from Inorder and Postorder Traversal 题解题目描述给定两个整数数组inorder和postorder其中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]解题思路方法递归思路后序遍历的最后一个元素是根节点在中序遍历中找到根节点的位置根节点左边的元素是左子树的中序遍历右边的元素是右子树的中序遍历根据右子树的长度在后序遍历中找到左子树的后序遍历和右子树的后序遍历递归地构造右子树和左子树注意顺序因为后序遍历的顺序是左子树、右子树、根节点复杂度分析时间复杂度O(n)其中 n 是二叉树的节点个数。每个节点只被处理一次。空间复杂度O(n)需要使用哈希表来存储中序遍历中元素的位置以及递归调用的栈空间。代码实现方法递归# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def buildTree(self, inorder: List[int], postorder: List[int]) - Optional[TreeNode]: # 创建哈希表存储中序遍历中元素的位置 inorder_map {val: idx for idx, val in enumerate(inorder)} postorder_idx len(postorder) - 1 def build(left, right): nonlocal postorder_idx # 递归终止条件 if left right: return None # 后序遍历的最后一个元素是根节点 root_val postorder[postorder_idx] root TreeNode(root_val) postorder_idx - 1 # 在中序遍历中找到根节点的位置 inorder_idx inorder_map[root_val] # 递归构造右子树和左子树注意顺序因为后序遍历的顺序是左子树、右子树、根节点 root.right build(inorder_idx 1, right) root.left build(left, inorder_idx - 1) return root return build(0, len(inorder) - 1)测试用例测试用例 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]总结本题是二叉树的经典问题主要考察对二叉树遍历和递归的理解和应用。通过使用递归我们可以根据中序遍历和后序遍历的结果构造二叉树。递归的核心思想是后序遍历的最后一个元素是根节点在中序遍历中找到根节点的位置然后递归地构造右子树和左子树注意顺序因为后序遍历的顺序是左子树、右子树、根节点。这种方法不仅适用于从中序与后序遍历序列构造二叉树问题还可以应用于许多其他需要根据遍历结果构造二叉树的场景。掌握递归的思想对于解决这类问题非常重要。