6-1 二叉树中求度为2的结点的个数 分数 10  全屏浏览 作者 曾艳 单位 西安邮电大学 编写算法，在以二叉链表存储的二叉树中，求度为2的结点的个数。 函数接口定义： int Degree2(

在二叉链表表示的二叉树中，求度为2的节点个数可以通过深度优先搜索（DFS）或者广度优先搜索（BFS）来实现。这里我将提供一个基于递归的解决方案：

// 假设二叉链表节点结构体定义如下：
typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

int Degree2(TreeNode* root) {
    if (root == nullptr) return 0; // 如果根节点为空，返回0

    int degree2 = 0; // 初始化度为2的节点计数器
    bool hasRightChild = false;

    // 使用递归遍历左子树和右子树
    if (root->right != nullptr) {
        degree2 += 1; // 非空右子树的当前节点度为2
        hasRightChild = true;
    }

    degree2 += Degree2(root->left); // 计算左子树的度2节点，并累加到总和

    // 如果左子树存在且有右孩子，说明有一个新的度为2节点
    if (hasRightChild && root->left->right != nullptr) {
        degree2++;
    }

    return degree2;
}

这个算法通过检查每个节点是否有右子节点以及它的左子节点是否也有右子节点来计算度为2的节点。递归会一直深入直到叶子节点，然后返回上来更新计数。