构建二叉树
Table of Contents
#
刷题和刷题的副作用
我在刷题的时候，很搞笑，是先接触到对二叉树进行各种骚操作。意思是说，牛客或者力扣这些平台 已经默认给你的就是一棵二叉树，你只需要完成诸如前中后序各种遍历二叉树节点的算法。如果你对 这些概念感到陌生，没关系，成年人游戏喜欢吗？
可以想象成类似这样的成人游戏：顺着数数数到百，没有多少挑战，对吧？逆着数， 也没劲对吧？那就每十一个为组轮番顺序逆序数（要求在100妙内完成）…诸如此类。
问题是，如果你要在自己本地机器运行测试用例，那么，得先自己把二叉树给构建出来。为什么不老 老实实在平台刷题就得了？！因为我也想要更多1，我要把这些在刷题时显得鸡零狗碎的内容给组 织起来，当然大概只是为了自己开心。然后随便水博客:) 不得不说，虽然我是抱着刷题应试的极其功利的初心，也架不住有些内容确实很令人感兴趣。我把这 个称为刷题的副作用。
#
茴香豆和二叉树
茴香豆味道如何不得而知，但我貌似记得孔老哥说茴字有四种写法2。
关于构建二叉树，反正我就知道有四种，分别是：
- 给定一个数组，从这个数组构建一棵二叉树（默认大约就是完全二叉树）：
# 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
def build_tree(nodes, index=0):
if index >= len(nodes) or nodes[index] is None:
return None
root = TreeNode(nodes[index])
root.left = build_tree(nodes, 2 * index + 1)
root.right = build_tree(nodes, 2 * index + 2)
return root
- 给定两个数组，一个是前序遍历数组，另一个是中序遍历数组，构建二叉树：
# 可以通过以下步骤构建二叉树：
# 找到根节点：
# 在前序遍历中，第一个元素是根节点。
# 然后在中序遍历中找到该根节点的位置，
# 根据这个位置可以将中序遍历数组分为左右子树的部分：
# 根节点左边的部分是左子树。
# 根节点右边的部分是右子树。
# 递归构建左右子树：
# 在中序遍历的左子树部分和右子树部分中，继续构建左右子树。
# 使用前序遍历的第二个元素（第一个是当前的根）作为新的根节点继续递归。
# 终止条件：
# 当中序遍历或前序遍历数组为空时，返回 None，表示当前节点没有子节点。
def build_tree(self, preorder, inorder):
# 递归终止条件：没有节点了
if not preorder or not inorder:
return None
# 前序遍历：根-左-右
# 前序数组的第一个元素就是根节点
root_val = preorder[0]
root = TreeNode(root_val)
# 中序遍历：左-根-右
# 在中序数组中找根节点的位置
inorder_index = inorder.index(root_val)
# 构建左右子树
root.left = self.build_tree(
preorder[1 : inorder_index + 1], inorder[:inorder_index]
)
root.right = self.build_tree(
preorder[inorder_index + 1 :], inorder[inorder_index + 1 :]
)
return root
- 给定两个数组，一个是中序遍历数组，另一个是后序遍历数组，构建二叉树：
# 可以通过以下步骤构建二叉树：
# 找到根节点：
# 在后序遍历中，最后一个元素是根节点。
# 然后在中序遍历中找到该根节点的位置，
# 根据这个位置可以将中序遍历数组分为左右子树的部分：
# 根节点左边的部分是左子树。
# 根节点右边的部分是右子树。
# 递归构建左右子树：
# 在中序遍历的左子树部分和右子树部分中，继续构建左右子树。
# 使用后序遍历的倒数第二个元素（倒数第一个是当前的根）作为新的根节点继续递归。
# 终止条件：
# 当中序遍历或后序遍历数组为空时，返回 None，表示当前节点没有子节点。
def build_tree(self, inorder, postorder):
if not inorder or not postorder:
return None
# 后序遍历：左-右-根
# （递归）传入函数的后序数组的倒数第一个元素就是根节点
root_val = postorder[-1]
root = TreeNode(root_val)
# 中序遍历：左-根-右
# 在中序数组中找根节点的位置
inorder_index = inorder.index(root_val)
# 构建左右子树
root.left = self.build_tree(inorder[:inorder_index], postorder[:inorder_index])
root.right = self.build_tree(
inorder[inorder_index + 1 :], postorder[inorder_index:-1]
)
return root
- 给定两个数组，一个是前序遍历数组，另一个是后序遍历数组，构建二叉树：
# 构建的过程比较复杂，因为前序遍历和后序遍历不能直接区分左右子树的边界。具体思路如下：
# 根节点：
# 前序遍历的第一个元素是根节点，后序遍历的最后一个元素是根节点。
# 左子树的根节点：
# 前序遍历的第二个元素是左子树的根节点。根据这个节点在后序遍历中的位置，我们可以知
# 道左子树的大小，进而划分出前序遍历和后序遍历中的左右子树部分。
# 递归构建左右子树：
# 确定了左子树的范围后，递归构建左右子树，直到数组为空时，返回 None 表示没有子节点。
def build_tree(self, preorder, postorder):
# 如果前序遍历为空，返回None
if not preorder or not postorder:
return None
# 前序遍历的第一个节点是根节点
root = TreeNode(preorder[0])
# 如果只有一个节点，直接返回根节点
if len(preorder) == 1:
return root
# 前序遍历的第二个节点是左子树的根节点，找到它在后序遍历中的位置
left_root_val = preorder[1]
left_subtree_size = postorder.index(left_root_val) + 1
# 递归构建左子树和右子树
root.left = self.build_tree(
preorder[1 : 1 + left_subtree_size], postorder[:left_subtree_size]
)
root.right = self.build_tree(
preorder[1 + left_subtree_size :], postorder[left_subtree_size:-1]
)
return root
#
前中后序遍历算法大放送
# 前序遍历：根 -> 左 -> 右
def preorder_traversal(root):
if root is None:
return []
return [root.val] + preorder_traversal(root.left) + preorder_traversal(root.right)
# 中序遍历：左 -> 根 -> 右
def inorder_traversal(root):
if root is None:
return []
return inorder_traversal(root.left) + [root.val] + inorder_traversal(root.right)
# 后序遍历：左 -> 右 -> 根
def postorder_traversal(root):
if root is None:
return []
return postorder_traversal(root.left) + postorder_traversal(root.right) + [root.val]
当然也不能把层序遍历给落下：
# 层序遍历“标准”做法（带for循环）：处理逻辑更清晰
def level_order_bfs(root, prt_none=False):
if root is None:
return []
result = []
queue = deque([root])
while queue:
level_sz = len(queue) # 当前层的节点数
level_nodes = []
for _ in range(level_sz): # 遍历当前层所有节点
node = queue.popleft()
if node is not None:
level_nodes.append(node.val)
queue.append(node.left)
queue.append(node.right)
else:
if prt_none:
level_nodes.append(None)
result.extend(level_nodes)
if prt_none:
# 清理结果列表末尾多余的 None
while result and result[-1] is None:
result.pop()
return result
不知道你对这些算法感觉如何，我反正是觉得挺有意思。但关于前文“成人游戏”的噱头，我想表示抱 歉，因为通常大家多少是期待那是好玩的游戏，没想到裤子都脱了，你就给我整数数游戏。别急，关 于这种翻来覆去地搞类似事情的游戏，王二后来被人逮住关起来写的交代材料就比较有趣3，你可 以自己看去。