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

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 ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 树中节点数目在范围 [0, 2000] 内

• -1000 <= Node.val <= 1000

这道题就是考察我们对二叉树层序遍历的掌握情况，在上面的二叉树理论基础中的广度优先遍历中我们已经实现了这个过程，并且使用的迭代方法，下面我来说一下递归的方法如何实现。

实现思路跟迭代法一样就是代码更加简洁，具体思路我写在了代码注释里面。

# 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叉树的层序遍历

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

示例 1：

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

示例 2：

输入：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]]

提示：

• 树的高度不会超过 1000
• 树的节点总数在 [0, 10^4] 之间

这道题目也是套模板，只不过在左孩子和右孩子的基础上多了一个孩子。

"""
# 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)$。