二叉树构建（从3种遍历中构建）python刷题记录

R3-树与二叉树篇.

目录

从前序与中序遍历序列构造二叉树

算法思路：

灵神套路 

从中序与后序遍历序列构造二叉树

算法思路： 

灵神套路 

从前序和后序遍历序列构造二叉树

算法思路：  

灵神套路 

从前序与中序遍历序列构造二叉树

算法思路：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         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 left>right:return#建立根节点的子树node=TreeNode(preorder[root])i=dict[preorder[root]]#左子树递归node.left=recur(root+1,left,i-1)#右子树递归node.right=recur(i-left+root+1,i+1,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, val=0, left=None, right=None):
#         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_l==pre_r:return None#左子树大小left_size=dict[preorder[pre_l]]-in_lleft=dfs(pre_l+1,pre_l+1+left_size,in_l,in_l+left_size)right=dfs(pre_l+1+left_size,pre_r,in_l+1+left_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, val=0, left=None, right=None):
#         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_l==post_r:return None#左子树大小left_size=dict[postorder[post_r-1]]-in_lleft=dfs(in_l,in_l+left_size,post_l,post_l+left_size)right=dfs(in_l+left_size+1,in_r,post_l+left_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, val=0, left=None, right=None):
#         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_l==pre_r:return None#叶子结点if pre_l+1==pre_r:return TreeNode(preorder[pre_l])#左子树大小left_size=dict[preorder[pre_l+1]]-post_l+1left=dfs(pre_l+1,pre_l+1+left_size,post_l)right=dfs(pre_l+1+left_size,pre_r,post_l+left_size)return TreeNode(preorder[pre_l],left,right)#存储前序遍历的值与索引的映射dict={key:index for index,key in enumerate(postorder)}#左闭右开区间return dfs(0,len(preorder),0)