Leetcode 1302.层数最深子叶结点的和

大家好，今天我给大家分享一下我关于这个题的想法，我这个题过程比较复杂，但大家如果觉得好的话，就请给个免费的赞吧，谢谢了^ _ ^
1.题目要求:

给你一棵二叉树的根节点 root ，请你返回 层数最深的叶子节点的和 。

举例如图所示:

2.做题思路:
1.先用前序遍历求出树的结点数量:

void preorder(struct TreeNode* root,int* length){
    if(root == NULL){
        return;
    }
    (*length)++;
    preorder(root->left,length);
    preorder(root->right,length);
}
int* length = (int*)malloc(sizeof(int));
    *length = 0;
    preorder(root,length);

2.然后再根据结点数量用malloc分配两个数组，一个要进行层序遍历，一个要记录树每一层的宽度:

//此数组是用来存层序遍历的
int* treeval = (int*)malloc(sizeof(int)* (*length));
    int j = 0;
    //此数组是用来进行记录树的每层的宽度
    int* col = (int*)malloc(sizeof(int) * (*length + 1));
    int j_1 = 0;

3.然后我们进行层序遍历,设置变量把每一行结点的数量记录下来，再把每个结点存入数组中:

typedef struct queue{
    struct TreeNode* data;
    struct queue* next;
}queue_t;
//入队
void insert_tail(queue_t** head,struct TreeNode* data)
{
    queue_t* newnode = (queue_t*)malloc(sizeof(queue_t));
    memset(newnode,0,sizeof(queue_t));
    newnode->data = data;
    newnode->next = NULL;
    if(*head == NULL){
        *head = newnode;
        return;
    }
    queue_t* cur = *head;
    while(cur->next != NULL){
        cur = cur->next;
    }
    cur->next = newnode;
}
//出队
struct TreeNode* pop(queue_t** head){
    if(*head == NULL){
        struct TreeNode* x = (*head)->data;
        (*head) = (*head)->next;
        return x;
    }
    struct TreeNode* x = (*head)->data;
    (*head) = (*head)->next;
    return x;
}
//开始层序遍历

    int nextcount = 0;//记录树每一层的结点数量
    queue_t* quence = NULL;
    int size = 0;
    insert_tail(&quence,root);
    size++;
    while(size != 0){
        for(i = 0;i < count;i++){
            struct TreeNode* node = pop(&quence);
            treeval[j] = node->val;
            j++;
            size--;
            if(node->left != NULL){
                insert_tail(&quence,node->left);
                size++;
                nextcount++;
            }
            if(node->right != NULL){
                insert_tail(&quence,node->right);
                size++;
                nextcount++;
            }
        }
        col[j_1] = nextcount;
        j_1++;
        count = nextcount;
        nextcount = 0;
    }

3.全部代码:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
typedef struct queue{
    struct TreeNode* data;
    struct queue* next;
}queue_t;
//出队
void insert_tail(queue_t** head,struct TreeNode* data)
{
    queue_t* newnode = (queue_t*)malloc(sizeof(queue_t));
    memset(newnode,0,sizeof(queue_t));
    newnode->data = data;
    newnode->next = NULL;
    if(*head == NULL){
        *head = newnode;
        return;
    }
    queue_t* cur = *head;
    while(cur->next != NULL){
        cur = cur->next;
    }
    cur->next = newnode;
}
//入队
struct TreeNode* pop(queue_t** head){
    if(*head == NULL){
        struct TreeNode* x = (*head)->data;
        (*head) = (*head)->next;
        return x;
    }
    struct TreeNode* x = (*head)->data;
    (*head) = (*head)->next;
    return x;
}
//进行前序遍历
void preorder(struct TreeNode* root,int* length){
    if(root == NULL){
        return;
    }
    (*length)++;
    preorder(root->left,length);
    preorder(root->right,length);
}
int deepestLeavesSum(struct TreeNode* root) {
    int* length = (int*)malloc(sizeof(int));
    *length = 0;
    preorder(root,length);
    int* treeval = (int*)malloc(sizeof(int)* (*length));
    int j = 0;
    int* col = (int*)malloc(sizeof(int) * (*length + 1));
    int j_1 = 0;
    int count = 1;
    col[j_1] = count;
    j_1++;
    int i = 0;
    //记录树的每一层的宽度
    int nextcount = 0;
    queue_t* quence = NULL;
    int size = 0;
    insert_tail(&quence,root);
    size++;
    while(size != 0){
        for(i = 0;i < count;i++){
            struct TreeNode* node = pop(&quence);
            treeval[j] = node->val;
            j++;
            size--;
            if(node->left != NULL){
                insert_tail(&quence,node->left);
                size++;
                nextcount++;
            }
            if(node->right != NULL){
                insert_tail(&quence,node->right);
                size++;
                nextcount++;
            }
        }
        col[j_1] = nextcount;
        j_1++;
        count = nextcount;
        nextcount = 0;
    }
    int count1 = col[j_1 - 2];
    int sum = 0;
    int f = 0;
    for(i = j - 1;i >= 0;i--){
       sum += treeval[i];
       f++;
       if(f == count1){
            break;
       }
    }
    return sum;
}

好了，这就是我全部代码大家如果觉得好的话，就请给个免费的赞吧，谢谢了^ _ ^ .

原文地址：https://blog.csdn.net/m0_54244065/article/details/140511325

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！