二叉链表作为存储结构，中序建立一棵二叉树

Question

统计二叉树的叶子结点个数。
按层次遍历二叉树的方法，统计二叉树中度为1的节点个数。

Answer 1

统计二叉树的叶子结点个数，有多种方法，其中一种是使用递归的方法。递归的思想是，如果一个二叉树为空，那么它的叶子结点个数为0；如果一个二叉树只有一个根结点，那么它的叶子结点个数为1；如果一个二叉树有左右子树，那么它的叶子结点个数等于左右子树的叶子结点个数之和。根据这个思想，我们可以用C++语言编写如下的函数：

// 定义二叉树结点的结构体
struct TreeNode {
    int val; // 结点的值
    TreeNode *left; // 左子树的指针
    TreeNode *right; // 右子树的指针
    TreeNode(int x) : val(x), left(NULL), right(NULL) {} // 构造函数
};

// 定义统计叶子结点个数的函数
int countLeaves(TreeNode* root) {
    // 如果根结点为空，返回0
    if (root == NULL) {
        return 0;
    }
    // 如果根结点没有左右子树，返回1
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    // 如果根结点有左右子树，返回左右子树的叶子结点个数之和
    return countLeaves(root->left) + countLeaves(root->right);
}

按层次遍历二叉树的方法，统计二叉树中度为1的结点个数，也有多种方法，其中一种是使用队列的方法。队列的思想是，从根结点开始，将每一层的结点依次入队，然后出队时判断结点的度是否为1，如果是，就累加计数。根据这个思想，我们可以用C++语言编写如下的函数：

// 引入队列的头文件
#include <queue>
using namespace std;

// 定义二叉树结点的结构体
struct TreeNode {
    int val; // 结点的值
    TreeNode *left; // 左子树的指针
    TreeNode *right; // 右子树的指针
    TreeNode(int x) : val(x), left(NULL), right(NULL) {} // 构造函数
};

// 定义统计度为1的结点个数的函数
int countDegreeOne(TreeNode* root) {
    // 如果根结点为空，返回0
    if (root == NULL) {
        return 0;
    }
    // 定义一个队列，用于存储每一层的结点
    queue<TreeNode*> q;
    // 将根结点入队
    q.push(root);
    // 定义一个变量，用于累加度为1的结点个数
    int count = 0;
    // 当队列不为空时，循环执行以下操作
    while (!q.empty()) {
        // 取出队首的结点
        TreeNode* node = q.front();
        // 将队首的结点出队
        q.pop();
        // 判断结点的度是否为1，即左子树为空且右子树不为空，或者左子树不为空且右子树为空
        if ((node->left == NULL && node->right != NULL) || (node->left != NULL && node->right == NULL)) {
            // 如果是，将计数加一
            count++;
        }
        // 如果结点的左子树不为空，将左子树的根结点入队
        if (node->left != NULL) {
            q.push(node->left);
        }
        // 如果结点的右子树不为空，将右子树的根结点入队
        if (node->right != NULL) {
            q.push(node->right);
        }
    }
    // 返回计数的结果
    return count;
}