非空二叉树中度为0的结点

在非空二叉树中，度是指一个节点拥有的子节点数。如果一个节点没有子节点，那么它的度就是0，这种节点通常被称为叶子节点或终端节点。在二叉树结构中，度为0的节点具有以下特点：

1. **唯一性**：除了根节点外（除非根节点本身也是叶子节点），每个非空二叉树中只有一个度为0的节点，即每个叶子节点都有其父节点。
2. **结构作用**：它们是树的最底层元素，负责存储数据，并作为其他节点查找或操作的终点。
3. **遍历**：在中序遍历（左-根-右）和后序遍历（左-右-根）中，叶子节点总是最后一个被访问到，因为它们没有子节点需要继续遍历。

相关问题

统计二叉树中度为2的结点个数

统计二叉树中度为2的节点个数，可以通过递归方式实现。对于每个节点，判断其左右子树的度数，如果度数都为2，则当前节点的度数也为2。

以下是该问题的递归实现代码：

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

def count_degree_2_nodes(root):
    if root is None:
        return 0
    count = 0
    if root.left and root.right:
        count += 1
    count += count_degree_2_nodes(root.left)
    count += count_degree_2_nodes(root.right)
    return count

其中，`count_degree_2_nodes` 函数接收一个二叉树的根节点作为参数，返回该二叉树中度为2的节点个数。如果根节点为空，则返回0。否则，对于非空节点，判断其左右子树的度数，如果都为2，则将计数器加1，并递归遍历其左右子树。最后返回计数器的值即可。

1. 假设二叉树中结点的类型为int，以二叉链表作为存储结构。求二叉树中值最大的结点。 2. 假设二叉树中结点的类型为char，采用顺序存储。设计二叉树的先序、中序、后序和层次遍历算法。 3. 在二叉链表上统计二叉树中度为2的结点个数（基于任何遍历均可）。Python

1. 要在二叉链表表示的整型二叉树中找到最大值节点，你可以从根节点开始，然后按照递归的方式进行遍历。首先比较当前节点的值与它的右子节点（如果存在的话），因为右子节点通常是较大的那个。如果右子节点比当前节点大，则继续向右查找；否则，返回当前节点。若整个树为空，说明不存在节点，可以设置一个默认的最大值初始化。

def find_max_value(root):
    if root is None:
        return float('-inf')
    max_val = root.val
    if root.right:
        max_val = max(max_val, find_max_value(root.right))
    if root.left:
        max_val = max(max_val, find_max_value(root.left))
    return max_val

2. 对于字符类型的二叉树，由于顺序存储，每个结点的左孩子和右孩子的索引可以通过简单加减得到。以下是遍历算法的伪代码：

- 先序遍历（根-左-右）：

def pre_order_traversal(root, arr):
    if root:
        arr.append(root.value)
        pre_order_traversal(root.left, arr)
        pre_order_traversal(root.right, arr)

# 中序遍历（左-根-右）：
def in_order_traversal(root, arr):
    if root:
        in_order_traversal(root.left, arr)
        arr.append(root.value)
        in_order_traversal(root.right, arr)

# 后序遍历（左-右-根）：
def post_order_traversal(root, arr):
    if root:
        post_order_traversal(root.left, arr)
        post_order_traversal(root.right, arr)
        arr.append(root.value)

3. 统计度为2的结点数量，需要在遍历时检查每个结点是否有两个非空的孩子。在上述遍历过程中，每遇到一个度为2的结点，就在适当的位置增加计数器。这里提供了一个层次遍历的例子：

from collections import deque

def count_degree_two_nodes(root):
    if not root:
        return 0
    queue = deque([root])
    degree_two_count = 0
    while queue:
        current = queue.popleft()
        if current.left and current.right:
            degree_two_count += 1
        if current.left:
            queue.append(current.left)
        if current.right:
            queue.append(current.right)
    return degree_two_count