二叉树：知道两种遍历，求全貌
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
1 根据前序和中序遍历序列构造二叉树
class Solution:
'''根据前序与中序遍历序列构造二叉树'''
def buildTree_(self, preorder: List[int], inorder: List[int]) -> TreeNode:
# preorder_left, preorder_right, inorder_left, inorder_right 维护下标
# 构建数值到中序下标的映射关系
item_to_index = {item: index for index, item in enumerate(inorder)}
def build(preorder_left, preorder_right, inorder_left, inorder_right):
'''
根据preorder_left找到根，然后对应到中序里的下标则是root_index_inorder
所以中序的下标：
下标从inorder_left 到 root_index_inorder - 1 是 左子树
下标从root_index_inorder + 1 到 inorder_right是 右子树
在前序中，去掉了跟节点，则：
preorder_left + 1 到 preorder_left + len(中序得到的左子树) 是左子树
preorder_left + len(中序得到的左子树) + 1 到 preorder_right 是右子树
'''
if preorder_left <= preorder_right and inorder_left <= inorder_right:
root_index_inorder = item_to_index[preorder[preorder_left]]
left_subtree_size = root_index_inorder - inorder_left
root = TreeNode(preorder[preorder_left])
root.left = build(preorder_left + 1, preorder_left + left_subtree_size, inorder_left, root_index_inorder - 1)
root.right = build(preorder_left + left_subtree_size + 1, preorder_right, root_index_inorder + 1, inorder_right)
return root
# 注意大下标一定是n-1
return build(0, len(preorder)-1, 0, len(inorder)-1)
2 根据中序和后序遍历序列构造二叉树
class Solution:
'''根据中序和后序遍历序列构造二叉树'''
def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
# 把postorder反过来其实就是中右左
re_postorder = postorder[::-1]
# 构建数值到中序下标的映射关系
item_to_index = {item: index for index, item in enumerate(inorder)}
def build(re_postorder_left, re_postorder_right, inorder_left, inorder_right):
if re_postorder_left <= re_postorder_right and inorder_left <= inorder_right:
root_index_inorder = item_to_index[re_postorder[re_postorder_left]]
right_subtree_size = inorder_right - root_index_inorder
# re_postorder: 中右左
# inorder：左中右
root = TreeNode(re_postorder[re_postorder_left])
root.left = build(re_postorder_left + right_subtree_size + 1, re_postorder_right, inorder_left, root_index_inorder - 1)
root.right = build(re_postorder_left + 1, re_postorder_left + right_subtree_size, root_index_inorder + 1 ,inorder_right)
return root
return build(0, len(re_postorder)-1, 0, len(inorder)-1)
3 根据前序和后序遍历序列构造二叉树
class Solution:
def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> TreeNode:
# 中左右，中右左
# preorder: 1 2 4 5 3 6 7
# re_postorder: 1 3 7 6 2 5 4
# 先反序postorder
re_postorder = postorder[::-1]
# 构建数值到反后序下标的映射关系
item_to_index = {item: index for index, item in enumerate(re_postorder)}
def build(preorder_left, preorder_right, re_postorder_left, re_postorder_right):
if preorder_left <= preorder_right and re_postorder_left <= re_postorder_right:
root = TreeNode(preorder[preorder_left])
if preorder_left == preorder_right:
# 要考虑对于最后一个叶子节点来说没有左子树，也就没有下面的preorder_left+1这个键
return root
left_subtree_spot = item_to_index[preorder[preorder_left+1]] # 左子树开头的位置
left_tree_size = re_postorder_right - left_subtree_spot + 1
root.left = build(preorder_left+1, preorder_left + left_tree_size, left_subtree_spot, re_postorder_right)
root.right = build(preorder_left + left_tree_size + 1, preorder_right, re_postorder_left + 1, re_postorder_right - left_tree_size)
return root
return build(0, len(preorder)-1, 0, len(re_postorder)-1)