---

叶子节点是指二叉树中没有子节点的节点。统计二叉树的叶子节点个数是一个经典问题，广泛用于数据分析、树的结构验证等场景。本文将介绍如何通过递归和非递归方法统计二叉树的叶子节点，并扩展其应用。

---

一、叶子节点的定义

叶子节点是二叉树中没有左子节点和右子节点的节点。

示例

给定如下二叉树：

       1
      / \
     2   3
    / \    \
   4   5    6

叶子节点：4、5、6
叶子节点个数：3

---

二、递归方法统计叶子节点

递归是一种常用方法，尤其适合解决树的层级问题。我们可以使用如下逻辑：

1. 如果当前节点为空，返回0。
2. 如果当前节点是叶子节点，返回1。
3. 对左子树和右子树分别递归统计，最后将结果相加。

2.1 Java实现

class TreeNode {
    int val;
    TreeNode left, right;

    TreeNode(int val) {
        this.val = val;
    }
}

public class LeafNodeCounter {
    public static int countLeaves(TreeNode root) {
        if (root == null) {
            return 0; // 空树没有叶子节点
        }

        if (root.left == null && root.right == null) {
            return 1; // 当前节点是叶子节点
        }

        // 递归统计左右子树的叶子节点
        return countLeaves(root.left) + countLeaves(root.right);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(6);

        System.out.println("叶子节点个数：" + countLeaves(root));
    }
}

输出结果：

叶子节点个数：3

---

2.2 Python实现

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

def count_leaves(root):
    if not root:
        return 0  # 空树没有叶子节点

    if not root.left and not root.right:
        return 1  # 当前节点是叶子节点

    # 递归统计左右子树的叶子节点
    return count_leaves(root.left) + count_leaves(root.right)

# 构建示例二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)

print("叶子节点个数：", count_leaves(root))

输出结果：

叶子节点个数：3

---

三、非递归方法统计叶子节点

通过非递归方式，可以利用栈或队列遍历二叉树的所有节点，同时统计叶子节点的个数。

3.1 Java实现（基于队列）

import java.util.LinkedList;
import java.util.Queue;

public class LeafNodeCounterIterative {
    public static int countLeaves(TreeNode root) {
        if (root == null) {
            return 0; // 空树没有叶子节点
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        int leafCount = 0;

        while (!queue.isEmpty()) {
            TreeNode current = queue.poll();

            if (current.left == null && current.right == null) {
                leafCount++; // 当前节点是叶子节点
            }

            if (current.left != null) {
                queue.add(current.left);
            }

            if (current.right != null) {
                queue.add(current.right);
            }
        }

        return leafCount;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(6);

        System.out.println("叶子节点个数：" + countLeaves(root));
    }
}

输出结果：

叶子节点个数：3

---

3.2 Python实现（基于队列）

from collections import deque

def count_leaves_iterative(root):
    if not root:
        return 0  # 空树没有叶子节点

    queue = deque([root])
    leaf_count = 0

    while queue:
        current = queue.popleft()

        if not current.left and not current.right:
            leaf_count += 1  # 当前节点是叶子节点

        if current.left:
            queue.append(current.left)
        if current.right:
            queue.append(current.right)

    return leaf_count

# 构建示例二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)

print("叶子节点个数：", count_leaves_iterative(root))

输出结果：

叶子节点个数：3

---

四、扩展功能：打印叶子节点值

在统计叶子节点的同时，我们可以将所有叶子节点的值存储到列表或直接打印。

4.1 Java实现

import java.util.ArrayList;
import java.util.List;

public class PrintLeaves {
    public static void printLeafNodes(TreeNode root) {
        if (root == null) {
            return;
        }

        if (root.left == null && root.right == null) {
            System.out.print(root.val + " "); // 当前节点是叶子节点
        }

        printLeafNodes(root.left);
        printLeafNodes(root.right);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(6);

        System.out.print("叶子节点值：");
        printLeafNodes(root);
    }
}

输出结果：

叶子节点值：4 5 6

---

4.2 Python实现

def print_leaves(root):
    if not root:
        return

    if not root.left and not root.right:
        print(root.val, end=" ")  # 当前节点是叶子节点
        return

    print_leaves(root.left)
    print_leaves(root.right)

print("叶子节点值：", end="")
print_leaves(root)

输出结果：

叶子节点值：4 5 6

---

五、总结

本文详细讲解了如何统计二叉树的叶子节点个数，包括递归和非递归两种实现方法。此外，还扩展了打印叶子节点值的功能。总结如下：

1. 递归实现：简洁直观，适合大多数树操作。
2. 非递归实现：通过栈或队列进行遍历，适合树的层次遍历或大数据量处理。
3. 扩展功能：在统计的同时记录或打印叶子节点值。

通过本文的学习，相信你已经掌握了这一经典问题的多种解决方案，并能灵活应用于实际开发中。