数据结构 假设二叉树用二叉链表存储，设计一个算法，求二叉树的结点个数。 整体代码

下面是基于二叉链表存储结构的二叉树结点个数求解算法的代码实现：

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def count_nodes(root: TreeNode) -> int:
    if not root:
        return 0
    return 1 + count_nodes(root.left) + count_nodes(root.right)

上述代码定义了一个二叉树结点类 `TreeNode`，包含结点值和左右子结点的指针。然后定义了一个递归函数 `count_nodes`，用于计算二叉树的结点个数。如果当前结点为空，返回 0；否则返回 1（当前结点）加上左子树结点个数和右子树结点个数之和。

相关问题

假设二叉树采用二叉链表存储结构存储，其中可能存在多个相同值的结点。设计一个算法求其中最大结点值的结点个数

在二叉链表存储的二叉树中，如果存在多个相同值的节点，可以借助迭代或递归的方式遍历整个树来寻找最大值及其对应的节点数。这里提供一种基于深度优先搜索（DFS）的算法：

1. 初始化两个变量，`max_val`用于记录当前找到的最大值，`count`用于统计最大值节点的数量，初始值均为根节点的值。

2. 定义一个辅助函数 `dfs(node)`，输入一个节点`node`：
- 检查`node.value`是否大于`max_val`，如果是，则更新`max_val`和`count`。
- 对于`node.left`和`node.right`，递归地调用`dfs`，更新最大值及计数。

3. 开始从根节点调用`dfs(root)`。

4. 遍历结束后，返回`count`作为结果。

def find_max_values_count(root):
    max_val = root.value if root else None
    count = 0

    def dfs(node):
        nonlocal max_val, count
        if node and node.value > max_val:
            max_val = node.value
            count = 1
        else:
            if node and node.value == max_val:
                count += 1
        if node.left:
            dfs(node.left)
        if node.right:
            dfs(node.right)

    dfs(root)
    return count

假设二叉树采用二叉链表存储结构，设计一个算法，求二叉树t中距*p最近的叶子结点。

当二叉树采用链式存储结构时，可以使用深度优先搜索（DFS）或层次遍历的方法来找到离给定节点p最近的叶子节点。这里提供一种基于递归的解决方案：

算法步骤如下：

1. 如果p为空，则直接返回null；
2. 检查p是否是叶子节点，如果是，就直接返回p；
3. 分别递归地对左子树和右子树执行该操作，并记录下每个子树中最靠近根节点的叶子节点的距离和实际节点；
4. 对于左子树，如果它的最接近根的叶子节点距离小于当前p到根的距离加上1，更新结果；
5. 同理，对于右子树，也进行同样的比较；
6. 返回距离更近的那个子树的结果，即为整个树中最靠近p的叶子节点。

Python伪代码示例：

def nearest_leaf_node(p, t):
    if p is None or p.left is None and p.right is None:
        return p

    left_distance = None if p.left is None else nearest_leaf_node(p.left, t)
    right_distance = None if p.right is None else nearest_leaf_node(p.right, t)

    # 更新最近的叶子节点距离和节点
    closest = (left_distance, p.left) if left_distance is not None and (right_distance is None or left_distance.distance < right_distance.distance + 1) else (right_distance, p.right)

    # 返回结果
    return closest[1] if closest[0].distance == closest[1].depth else closest[0]