做网站ppt淄博网站制作服务

做网站ppt,淄博网站制作服务,wordpress微信拦截,做网站年入百万题目给定两个整数数组 preorder 和 inorder #xff0c;其中 preorder 是二叉树的先序遍历#xff0c; inorder 是同一棵树的中序遍历#xff0c;请构造二叉树并返回其根节点。示例 1:输入: preorder [3,9,20,15,7], inorder [9,3,15,20,7] 输出: [3,9,20,null,null,15,7]…题目给定两个整数数组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]提示:1 preorder.length 3000inorder.length preorder.length-3000 preorder[i], inorder[i] 3000preorder和inorder均无重复元素inorder均出现在preorderpreorder保证为二叉树的前序遍历序列inorder保证为二叉树的中序遍历序列思路1.前序序列——找根2.中序序列——划分左右子树3.递归遍历具体步骤1递归结束条件如果前序or中序序列为空说明已遍历结束return None2创建根节点取前序序列的第一个元素3分左右子树在inorder中找根节点的索引值根据这个索引值将preorder和inorder拆分成左右两个子树left_in inorder[:root_index],right_in inorder[root_index 1:]left_pre preorder[1:len(root_index) 1],right_pre preorder[len(root_index)1,:]递归处理左右子树代码# 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]: if not preorder or not inorder: # 如果序列为空return None return None root_val preorder[0] # 取根节点 root TreeNode(root_val) root_idx inorder.index(root_val) # 在中序中找根节点索引 left_in inorder[:root_idx] # 根据根节点索引划分左右子树 right_in inorder[root_idx 1:] left_pre preorder[1: len(left_in) 1] right_pre preorder[len(left_in) 1:] root.left self.buildTree(left_pre, left_in) # 递归处理左右子树 root.right self.buildTree(right_pre, right_in) return root