LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal 题解

LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal 题解题目描述给定两个整数数组preorder和inorder其中preorder是二叉树的先序遍历inorder是同一棵树的中序遍历请构造二叉树并返回其根节点。示例 1输入: preorder [3,9,20,15,7], inorder [9,3,15,20,7] 输出: [3,9,20,null,null,15,7]示例 2输入: preorder [-1], inorder [-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, preorder: List[int], inorder: List[int]) - Optional[TreeNode]: # 创建哈希表存储中序遍历中元素的位置 inorder_map {val: idx for idx, val in enumerate(inorder)} preorder_idx 0 def build(left, right): nonlocal preorder_idx # 递归终止条件 if left right: return None # 先序遍历的第一个元素是根节点 root_val preorder[preorder_idx] root TreeNode(root_val) preorder_idx 1 # 在中序遍历中找到根节点的位置 inorder_idx inorder_map[root_val] # 递归构造左子树和右子树 root.left build(left, inorder_idx - 1) root.right build(inorder_idx 1, right) return root return build(0, len(inorder) - 1)测试用例测试用例 1输入preorder [3,9,20,15,7], inorder [9,3,15,20,7]输出[3,9,20,null,null,15,7]测试用例 2输入preorder [-1], inorder [-1]输出[-1]总结本题是二叉树的经典问题主要考察对二叉树遍历和递归的理解和应用。通过使用递归我们可以根据先序遍历和中序遍历的结果构造二叉树。递归的核心思想是先序遍历的第一个元素是根节点在中序遍历中找到根节点的位置然后递归地构造左子树和右子树。这种方法不仅适用于从前序与中序遍历序列构造二叉树问题还可以应用于许多其他需要根据遍历结果构造二叉树的场景。掌握递归的思想对于解决这类问题非常重要。