Python求叶子节点个数

本文将详细介绍如何使用Python求解二叉树中的叶子节点个数。

一、概述

叶子节点是指二叉树中没有子节点的节点，也就是没有左子节点和右子节点的节点。求解二叉树中的叶子节点个数是一个常见的算法问题，可以通过递归或迭代的方式实现。下面将介绍两种方法。

二、递归法

递归法是一种简单粗暴的方法，可以很直观地求解叶子节点个数。通过递归地遍历二叉树的每个节点，当遍历到叶子节点时，个数加一。

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def count_leaves(node):
    if node is None:
        return 0
    if node.left is None and node.right is None:
        return 1
    return count_leaves(node.left) + count_leaves(node.right)

使用上述代码，先定义一个Node类表示二叉树的节点，其中包含value、left和right属性。然后定义一个count_leaves函数，使用递归的方式求解叶子节点个数。当节点为空时，返回0；当节点没有左子节点和右子节点时，返回1；否则递归地求解左子树和右子树的叶子节点个数，并相加。

三、迭代法

迭代法是另一种常用的求解叶子节点个数的方法，可以使用广度优先搜索（BFS）或深度优先搜索（DFS）实现。下面以深度优先搜索为例。

def count_leaves_iterative(root):
    if root is None:
        return 0
    stack = [root]
    count = 0
    while stack:
        node = stack.pop()
        if node.left is None and node.right is None:
            count += 1
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return count

使用上述代码，定义一个count_leaves_iterative函数，使用迭代的方式求解叶子节点个数。如果根节点为空，返回0；否则，初始化一个栈，并将根节点压入栈中。然后通过循环迭代，从栈中弹出节点，如果该节点没有左子节点和右子节点，则叶子节点个数加一。如果节点有左子节点，则将左子节点压入栈中；如果节点有右子节点，则将右子节点压入栈中。最终返回叶子节点个数。

四、总结

本文介绍了使用Python求解二叉树中叶子节点个数的递归法和迭代法。递归法通过递归遍历每个节点，当遍历到叶子节点时，个数加一；迭代法通过栈的方式实现遍历，当遍历到叶子节点时，个数加一。可以根据实际情况选择适合的方法，解决问题。