计算法统计二叉树中度为1的节点个数

old-tom / 2024-11-11 / 原文

最近学习有关于二叉树类的知识，学习时使用的是C语言。
代码如下：

include <stdio.h>

include <stdlib.h> // 添加这一行，包含 malloc 的声明

typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;

// 创建树节点
TreeNode* createNode(int val) {
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
newNode->val = val;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}

// 计算度为1的节点个数
int countDegreeOneNodes(TreeNode* root) {
if (root == NULL) {
return 0;
}

// 如果节点没有左右子节点，则不是度为1的节点
if (root->left == NULL && root->right == NULL) {
    return 0;
}

// 如果只有一个左子节点或者一个右子节点，则是度为1的节点
if ((root->left != NULL && root->right == NULL) || (root->left == NULL && root->right != NULL)) {
    return 1 + countDegreeOneNodes(root->left) + countDegreeOneNodes(root->right);
}

// 否则，继续递归计算左右子树的度为1的节点个数
return countDegreeOneNodes(root->left) + countDegreeOneNodes(root->right);

}

int main() {
TreeNode *root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);

printf("Number of nodes with degree one: %d\n", countDegreeOneNodes(root));

return 0;

}
使用这个就可计算简单二叉树的节点个数。更难的可以使用此类推。