深圳企业网站,高校网站建设需求单,装修全包报价明细表2023,公司网站建设预算从先序与中序遍历序列构造二叉树
描述#xff1a; 给定两个整数数组 preorder 和 inorder #xff0c;其中 preorder 是二叉树的先序遍历#xff0c; inorder 是同一棵树的中序遍历#xff0c;请构造二叉树并返回其根节点。
递归法
解题思路#xff1a; 通过先序遍历我…从先序与中序遍历序列构造二叉树
描述 给定两个整数数组 preorder 和 inorder 其中 preorder 是二叉树的先序遍历 inorder 是同一棵树的中序遍历请构造二叉树并返回其根节点。
递归法
解题思路 通过先序遍历我们可以找到root因为列表中没有重复数字的原因根据root我们可以根据中序找到root的索引位置该索引位置左边就是左子树右边就是右子树。而且根据中序中root的索引位置可以在先序中确定先序里左子树索引位置为[1:1idx)右子树索引位置[1idx:-1]。根据位置通过递归法直到遍历到结束。 ps:图片来源leetcode题解
代码实现
class TreeNode:def __init__(self,x):self.val xself.left Noneself.right None
class Solution:def buildTree(self,preorder:List[int],inorder:List[int])-:# 递归中止条件if not preorder or not inorder:return# 根据先序列表得到根节点rootroot TreeNode(preorder[0])# 根据中序列表得到根节点的索引位置idx inorder.index(preorder[0])# 递归法找到根节点的左子树部分root.left self.buildTree(preorder[1:1idx],inorder[0:idx])# 递归法找到根节点的右子树部分root.right self.buildTree(preorder[1idx:],inorder[idx1:])return root另一道题目从中序与后序遍历序列构造二叉树可以点击链接查看另一篇文章
