Python蓝桥杯训练：基本数据结构 [二叉树] 上

一、前言

目前蓝桥杯训练刷题刷到了二叉树，中间的栈和队列我没有更新，时间有点不太够，但是我又觉得如果刷题不写笔记的话感觉等于没刷，所以我还是将我刷题的过程以笔记的形式总结出来，内容可能没有之前几次的丰富但是我还是会将重要的内容总结出来，理论部分会有所减少，我会更加专注 于总结刷题过程中的思考。

二、有关二叉树理论基础

二叉树是一种树状数据结构，它的每个节点最多只有两个子节点。其中一个被称为左子节点，另一个被称为右子节点。以下是有关二叉树的理论基础的详细总结：

1、二叉树的基本定义

• 节点（Node）：二叉树的基本单位，它包含一个值（Value）和两个指针（Pointer），分别指向左子节点和右子节点（如果没有子节点，则指向 null 或空）。
• 根节点（Root）：二叉树中的第一个节点，它没有父节点，是整棵树的起点。
• 叶节点（Leaf）：没有子节点的节点称为叶节点。
• 内部节点（Internal Node）：除了叶节点以外的节点都称为内部节点。
• 高度（Height）：二叉树的高度是从根节点到最深叶节点的最长路径的长度。空树的高度为0，只有一个节点的二叉树的高度为1。
• 深度（Depth）：节点的深度是从根节点到该节点的唯一路径的长度。根节点的深度为0。
• 路径（Path）：是指从一个节点到另一个节点经过的所有节点的序列。
• 子树（Subtree）：是指由一个节点及其所有后代节点组成的二叉树。

2、二叉树的常见类型

• 普通二叉树（Binary Tree）：每个节点最多只有两个子节点。
• 完全二叉树（Complete Binary Tree）：除了最后一层，每一层的节点数都是满的，并且最后一层的节点都尽可能地靠左。
• 满二叉树（Full Binary Tree）：每个节点都有 0 或 2 个子节点，没有只有一个子节点的节点。
• 二叉搜索树（Binary Search Tree）：每个节点的左子树中的所有节点的值都小于该节点的值，右子树中的所有节点的值都大于该节点的值。
• 平衡二叉树（Balanced Binary Tree）：左右子树的高度差不超过 1 的二叉树。

3、二叉树的遍历方式

二叉树的深度优先遍历方式有三种：前序遍历、中序遍历和后序遍历，广度优先遍历有层序遍历。这些遍历方式都是基于递归的，它们都可以使用递归或迭代法来实现。

• 深度优先遍历

  • 前序遍历：先访问根节点，再递归地访问左子树和右子树。

    class Node:def __init__(self, value):self.left = Noneself.right = Noneself.value = valuedef preorder_traversal(node):if node is None:returnprint(node.value)preorder_traversal(node.left)preorder_traversal(node.right)root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)print("前序遍历结果：")
    preorder_traversal(root)
    

    前序遍历结果：
    1
    2
    4
    5
    3
    

  • 中序遍历：先递归地访问左子树，再访问根节点，最后递归地访问右子树。

    class Node:def __init__(self, value):self.left = Noneself.right = Noneself.value = valuedef inorder_traversal(node):if node is None:returninorder_traversal(node.left)print(node.value)inorder_traversal(node.right)root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)print("中序遍历结果：")
    inorder_traversal(root)
    

    中序遍历结果：
    4
    2
    5
    1
    3
    

  • 后序遍历：先递归地访问左子树和右子树，最后访问根节点。

    class Node:def __init__(self, value):self.left = Noneself.right = Noneself.value = valuedef postorder_traversal(node):if node is None:returnpostorder_traversal(node.left)postorder_traversal(node.right)print(node.value)root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)print("后序遍历结果：")
    postorder_traversal(root)
    

    后序遍历结果：
    4
    5
    2
    3
    1
    

• 广度优先遍历

  也称作层序遍历，是按照层次顺序从上往下、从左往右遍历树的节点。广度优先遍历需要借助队列来实现，每次从队列中取出一个节点，访问它的左右子节点，将子节点依次加入队列中，直到队列为空。

  from collections import dequeclass Node:def __init__(self, value):self.left = Noneself.right = Noneself.value = valuedef breadth_first_traversal(node):if node is None:returnqueue = deque()queue.append(node)while queue:current_node = queue.popleft()print(current_node.value)if current_node.left:queue.append(current_node.left)if current_node.right:queue.append(current_node.right)root = Node(1)
  root.left = Node(2)
  root.right = Node(3)
  root.left.left = Node(4)
  root.left.right = Node(5)print("广度优先遍历结果：")
  breadth_first_traversal(root)
  

  广度优先遍历结果：
  1
  2
  3
  4
  5
  

三、有关二叉树的层序遍历的题目

二叉树的层序遍历相比于其深度优先遍历会简单很多，基本记住一个模板很多题目就可以直接套用。

1、二叉树的层序遍历

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

输入：root = [1]
输出：[[1]]

输入：root = []
输出：[]

# 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 levelOrder(self, root: TreeNode) -> List[List[int]]:result = []  # 定义一个列表，用于保存最终结果def traverse(node, level):if not node:  # 如果当前节点为空，直接返回returnif level == len(result):  # 如果 result 中不存在当前层的列表，创建一个新的列表result.append([])result[level].append(node.val)  # 将当前节点的值加入当前层的列表中traverse(node.left, level + 1)  # 6递归遍历当前节点的左子树traverse(node.right, level + 1)  # 7. 递归遍历当前节点的右子树traverse(root, 0)  # 开始遍历二叉树return result  # 返回最终结果

2、N叉树的层序遍历

输入：root = [1,null,3,2,4,null,5,6]
输出：[[1],[3,2,4],[5,6]]

输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

"""
# Definition for a Node.
class Node:def __init__(self, val=None, children=None):self.val = valself.children = children
"""
# 迭代法
class Solution:def levelOrder(self, root: 'Node') -> List[List[int]]:if not root:return []res = []queue = [root]while queue:level = []size = len(queue)for i in range(size):node = queue.pop(0)level.append(node.val)for child in node.children:queue.append(child)res.append(level)return res

class Solution:def levelOrder(self, root: 'Node') -> List[List[int]]:if not root:  # 如果根节点为空，则直接返回空列表return []res = []  # 存储结果的列表def traverse(node, level):# 如果当前层数等于列表长度，则向列表中添加一个新列表if len(res) == level:res.append([])# 将当前节点的值加入到对应层的列表中res[level].append(node.val)# 递归遍历当前节点的所有子节点，并将它们的层数加一，作为递归函数的参数进行递归for child in node.children:traverse(child, level+1)# 从根节点开始递归遍历traverse(root, 0)return res  # 返回结果列表

3、填充每个节点的下一个右侧节点指针

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {int val;Node *left;Node *right;Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

示例 1：

输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。

示例 2:

输入：root = []
输出：[]

提示：

• 树中节点的数量在 [0, 212 - 1] 范围内
• -1000 <= node.val <= 1000

进阶：

• 你只能使用常量级额外空间。
• 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

这道题目的要求就是给定一棵二叉树，将每个节点的右子节点指向其在右边的下一个节点，如果右边没有节点，则将其指向None。要求使用常数级额外空间，也就是说不可以使用队列等数据结构。

题目要求在不使用队列等数据结构的情况下，将每个节点的右子节点指向其在右边的下一个节点。

我们可以从根节点开始，对于每一层节点，依次更新它们的右子节点，直到该层节点的最后一个节点。然后再进入下一层节点进行同样的操作。

具体来说我们指定一个指针 cur，表示当前层节点的最左边的节点，初始时 cur 指向根节点。在每一层的循环中，我们从左到右遍历该层的所有节点，对于每个节点，先将其左子节点的 next 指针指向其右子节点，再将其右子节点的 next 指针指向其 next 指针所指向节点的左子节点（如果该节点的 next 指针所指向节点不存在，则将其右子节点的 next 指针指向 None）。然后将该节点移动到下一个节点，直到该层的所有节点都被更新为止。最后将 cur 指针移动到下一层的最左边的节点，并重复上述操作，直到遍历完所有层为止。

"""
# Definition for a Node.
class Node:def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):self.val = valself.left = leftself.right = rightself.next = next
"""class Solution:def connect(self, root: 'Node') -> 'Node':if not root:return Nonecur = rootwhile cur.left:node = curwhile node:node.left.next = node.rightif node.next:node.right.next = node.next.leftnode = node.nextcur = cur.leftreturn root

时间复杂度：$O(n)$，其中 $n$ 是二叉树中的节点个数。

空间复杂度：$O(1)$。除了存储答案所需的空间外，我们只需要维护常数个变量，因此空间复杂度是 $O(1)$。