编写递归函数求二叉树的节点数目

递归是一种解决问题的强大技术，尤其适用于结构化的数据类型如二叉树。在二叉树中，每个节点最多有两个子节点（左孩子和右孩子）。为了计算一个二叉树的节点数目，我们可以定义一个递归函数，该函数会检查当前节点是否为空，如果为空则返回0；否则，返回当前节点加上其左子树和右子树的节点数。

以下是一个简单的C++递归函数示例：

#include <iostream>

// 定义二叉树节点的结构
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

int countNodes(TreeNode* root) {
    // 基本情况：空节点计数为0
    if (root == nullptr) {
        return 0;
    }
    
    // 递归情况：非空节点计数为其自身加左子树和右子树的节点数
    else {
        return 1 + countNodes(root->left) + countNodes(root->right);
    }
}

int main() {
    // 创建一个示例二叉树
    TreeNode* tree = new TreeNode(1);
    tree->left = new TreeNode(2);
    tree->right = new TreeNode(3);
    // ... 更多节点的添加

    std::cout << "The total number of nodes in the binary tree is: " << countNodes(tree) << std::endl;

    delete tree;  // 别忘了删除动态分配的内存
    return 0;
}

在这个例子中，`countNodes()` 函数首先检查根节点是否存在，然后分别递归地计算左子树和右子树的节点数，并返回它们之和加一（因为根节点自己也被计算了一次）。