网站开发中 视频播放卡,凡科董事长,搜索seo引擎,北京网站外包公司推荐R3-树与二叉树篇.
目录
从前序与中序遍历序列构造二叉树
算法思路#xff1a;
灵神套路
从中序与后序遍历序列构造二叉树
算法思路#xff1a;
灵神套路
从前序和后序遍历序列构造二叉树
算法思路#xff1a;
灵神套路
从前序与中序遍历序列构造二叉树 算法…R3-树与二叉树篇.
目录
从前序与中序遍历序列构造二叉树
算法思路
灵神套路
从中序与后序遍历序列构造二叉树
算法思路
灵神套路
从前序和后序遍历序列构造二叉树
算法思路
灵神套路
从前序与中序遍历序列构造二叉树 算法思路 # 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]:#仅限于无结点重复的序列def recur(root,left,right):#递归终止条件(遍历一遍中序遍历完成)if leftright:return#建立根节点的子树nodeTreeNode(preorder[root])idict[preorder[root]]#左子树递归node.leftrecur(root1,left,i-1)#右子树递归node.rightrecur(i-leftroot1,i1,right)return node#存储中序遍历的值与索引的映射dict{key:index for index,key in enumerate(inorder)}return recur(0,0,len(inorder)-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]:def dfs(pre_l,pre_r,in_l,in_r):if pre_lpre_r:return None#左子树大小left_sizedict[preorder[pre_l]]-in_lleftdfs(pre_l1,pre_l1left_size,in_l,in_lleft_size)rightdfs(pre_l1left_size,pre_r,in_l1left_size,in_r)return TreeNode(preorder[pre_l],left,right)#存储中序遍历的值与索引的映射dict{key:index for index,key in enumerate(inorder)}#左闭右开区间return dfs(0,len(preorder),0,len(inorder)) 从中序与后序遍历序列构造二叉树 算法思路 灵神套路
# 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]:def dfs(in_l,in_r,post_l,post_r):if post_lpost_r:return None#左子树大小left_sizedict[postorder[post_r-1]]-in_lleftdfs(in_l,in_lleft_size,post_l,post_lleft_size)rightdfs(in_lleft_size1,in_r,post_lleft_size,post_r-1)return TreeNode(postorder[post_r-1],left,right)#存储中序遍历的值与索引的映射dict{key:index for index,key in enumerate(inorder)}#左闭右开区间return dfs(0,len(inorder),0,len(postorder)) 从前序和后序遍历序列构造二叉树 算法思路 灵神套路
# 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 constructFromPrePost(self, preorder: List[int], postorder: List[int]) - Optional[TreeNode]:def dfs(pre_l,pre_r,post_l):if pre_lpre_r:return None#叶子结点if pre_l1pre_r:return TreeNode(preorder[pre_l])#左子树大小left_sizedict[preorder[pre_l1]]-post_l1leftdfs(pre_l1,pre_l1left_size,post_l)rightdfs(pre_l1left_size,pre_r,post_lleft_size)return TreeNode(preorder[pre_l],left,right)#存储前序遍历的值与索引的映射dict{key:index for index,key in enumerate(postorder)}#左闭右开区间return dfs(0,len(preorder),0)
