c++编写程序int countSingleC(btnode *T): 用递归算法计算T中度为1的结点数

假设 `btnode` 结构体如下所示：

typedef struct btnode {
    int val;            // 结点值
    struct btnode *l;   // 左子结点
    struct btnode *r;   // 右子结点
} btnode;

则可以按照以下步骤编写求解函数：

1. 确定递归终止条件：当结点为空（即 `T == NULL`）时，返回 0。
2. 递归遍历左子树，求解左子树中度为 1 的结点数，并将结果存储在变量 `left` 中。
3. 递归遍历右子树，求解右子树中度为 1 的结点数，并将结果存储在变量 `right` 中。
4. 统计当前结点的度数，如果为 1，则令结果加 1。
5. 返回 `left + right + count`，其中 `count` 是当前结点度数的统计结果。

按照以上思路，可以编写如下的求解函数：

int countSingleC(btnode *T) {
    if (T == NULL) {
        return 0;
    }

    int left = countSingleC(T->l);
    int right = countSingleC(T->r);
    int count = (T->l != NULL) + (T->r != NULL);

    return left + right + (count == 1);
}

这个函数的时间复杂度为 $O(n)$，其中 $n$ 是树中结点的数量。