可不可以帮我看看哪里不对。
计算二叉树左子叶权重和
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define NULL -1
typedef struct TreeNode {
int id;
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode, *TreeNodePtr;
typedef struct ListNode {
struct TreeNode *node; // 队列的值的类型是树节点指针
struct ListNode *next;
} ListNode, *ListNodePtr;
typedef struct Queue {
ListNodePtr dummyHead;
ListNodePtr tail;
int size;
} *QueuePtr;
// 创建链表的节点
ListNodePtr createListNode(TreeNodePtr node, ListNodePtr next) {
ListNodePtr curr = (ListNodePtr) (malloc(sizeof(ListNode)));
curr->node = node;
curr->next = next;
return curr;
}
// 创建树的节点
int TreeId = 0;
TreeNodePtr createTreeNode(int val, TreeNodePtr left, TreeNodePtr right) {
TreeNodePtr curr = (TreeNodePtr) (malloc(sizeof(TreeNode)));
curr->id = TreeId++;
curr->val = val;
curr->left = left;
curr->right = right;
return curr;
}
// 单链表队列初始化
QueuePtr InitQueue() {
QueuePtr queue = (QueuePtr) malloc(sizeof(struct Queue));
TreeNodePtr dummyTreeNode = createTreeNode(-1, NULL, NULL);
queue->size = 0;
queue->dummyHead = createListNode(dummyTreeNode, NULL);
queue->tail = queue->dummyHead;
return queue;
}
// 在 queue 的尾部添加一个元素的副本
void EnQueue(QueuePtr queue, TreeNodePtr node) {
ListNodePtr curr = createListNode(node, NULL);
queue->tail->next = curr;
queue->tail = queue->tail->next;
queue->size++;
}
// 删除 queue 中的第一个元素
void DeQueue(QueuePtr queue) {
if (queue->size == 0) {
perror("error! the size of queue is zero when call DeQueue().");
return;
}
ListNodePtr head = queue->dummyHead->next;
queue->dummyHead->next = head->next;
queue->size--;
if (queue->size == 0) queue->tail = queue->dummyHead;
free(head);
}
// 如果 queue 中没有元素, 返回 true
bool QueueEmpty(QueuePtr queue) {
return queue->size == 0;
}
// 返回 queue 中第一个元素的引用
TreeNodePtr GetHead(QueuePtr queue) {
if (QueueEmpty(queue)) {
perror("error! the size of queue is zero when call front().");
return NULL;
} else {
return queue->dummyHead->next->node;
}
}
int max(int a, int b) {
return (a >= b) ? a : b;
}
// 将输入转换为数组
void getDigits(char *buff, int *data) {
int len = strlen(buff);
int index = 0;
for (int i = 0; i < len; i++) {
int num = 0;
if (buff[i] == '#') {
num = -1;
i++;
} else {
while (buff[i] != ' ' && buff[i] != '\0') {
num = num * 10 + (buff[i++] - '0');
}
}
data[index++] = num;
}
}
// 删除二叉树
void destoryTree(TreeNodePtr root) {
if (!root) return;
if (root->left) {
destoryTree(root->left);
root->left = NULL;
}
if (root->right) {
destoryTree(root->right);
root->right = NULL;
}
free(root);
}
TreeNodePtr createTreeWithLevelOrder(int *data, int size) {
QueuePtr queue=InitQueue();
TreeNodePtr root=createTreeNode(data[0],NULL,NULL);
EnQueue(queue,root);
EnQueue(queue,root);
for(int i=1;i<size;i++)
{
TreeNodePtr father=GetHead(queue);
DeQueue(queue);
TreeNodePtr now=createTreeNode(data[i],NULL,NULL);
if(father->left==NULL) father->left=now;
else father->right=now;
EnQueue(queue,now);
EnQueue(queue,now);
}
return root;
}
int sumOfLeftLeaves(TreeNodePtr root) {
if(root==NULL || root->val==-1)
return 0;
int sum = 0;
if (root->left != NULL && root->left->left == NULL && root->left->right == NULL) {
// 左子结点是叶子结点，将其权重加入结果中
sum += root->left->val;
} else {
// 递归处理左子树和右子树
sum += sumOfLeftLeaves(root->left);
sum += sumOfLeftLeaves(root->right);
}
return sum;
}
int main() {
int SIZE = 128;
int MAX_NUM = 10;
char buff[SIZE];
int num;
bool use_graphviz = false;
int i = 0;
while (scanf("%d\n", &num) == 1) {
fgets(buff, SIZE, stdin);
char *pos = strchr(buff, '\n'); //查找换行符
if (pos) //如果find不为空指针
*pos = '\0'; //就把一个空字符放在这里
int size = num;
int data[size];
getDigits(buff, data);
TreeNodePtr tree_root = createTreeWithLevelOrder(data, size);
int weight_sum = sumOfLeftLeaves(tree_root);
printf("%d",weight_sum);
i++;
}
return 0;
}
