leetcode 1161.最大层内元素和

1.题目要求:

给你一个二叉树的根节点 root。设根节点位于二叉树的第 1 层，而根节点的子节点位于第 2 层，依此类推。

请返回层内元素之和 最大 的那几层（可能只有一层）的层号，并返回其中 最小 的那个。

2.此题思路:
创建队列，采用层序遍历的方式，把每一行的和算下来，保存在一个数组中，然后找出元素值最大的下标即可。
(1).先创建队列,以及入队函数和出队函数:

typedef struct queue{
    struct  TreeNode* data;
    struct  queue* next;
 }queue_t;
 //入队函数
 void push(queue_t** head,struct TreeNode* root){
    queue_t* newnode = (queue_t*)malloc(sizeof(queue_t));
    newnode->data = root;
    newnode-> next = NULL;
    if(*head == NULL){
        *head = newnode;
        return;
    }
    queue_t* tail = *head;
    while(tail->next != NULL){
        tail = tail->next;
    }
    tail->next = newnode;
 }
 //出队函数
 struct TreeNode* pop(queue_t** head){
    struct TreeNode* x = (*head)->data;
    (*head) = (*head)->next;
    return x;
 }

(2).然后进行层序遍历：

 int count = 1;
    int nextcount = 0;//记录下一行的节点数 
    int sum = 0;
    int* sumlevel = (int*)malloc(sizeof(int) * 1000);//保存每一行的和
    int j = 0;
    int size = 0;
    int i = 0;
    queue_t* enquence = NULL;
    //入队
    push(&enquence,root);
    size++;
    while(size != 0){
        for(i = 0;i < count;i++){
            struct TreeNode* temp = pop(&enquence);//出队
            sum += temp->val;
            size--;
            if(temp->left != NULL){
                push(&enquence,temp->left);
                nextcount++;
                size++;
            }
            if(temp->right != NULL){
                push(&enquence,temp->right);
                nextcount++;
                size++;
            }
        }
        count = nextcount;
        sumlevel[j] = sum;
        j++;
        nextcount = 0;
        sum = 0;
    }

(3).然后求出数组元素里最大值的下标:

int max = 0;
    for(i = 1;i < j;i++){
        if(sumlevel[i] > sumlevel[max]){
            max = i;
        }
    }

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 push(queue_t** head,struct TreeNode* root){
    queue_t* newnode = (queue_t*)malloc(sizeof(queue_t));
    newnode->data = root;
    newnode-> next = NULL;
    if(*head == NULL){
        *head = newnode;
        return;
    }
    queue_t* tail = *head;
    while(tail->next != NULL){
        tail = tail->next;
    }
    tail->next = newnode;
 }
 //出队函数
 struct TreeNode* pop(queue_t** head){
    struct TreeNode* x = (*head)->data;
    (*head) = (*head)->next;
    return x;
 }
int maxLevelSum(struct TreeNode* root) {
    int count = 1;
    int nextcount = 0;//记录下一行的节点数 
    int sum = 0;
    int* sumlevel = (int*)malloc(sizeof(int) * 1000);//此数组保存每一行元素之和
    int j = 0;
    int size = 0;
    int i = 0;
    queue_t* enquence = NULL;
    //入队
    push(&enquence,root);
    size++;
    while(size != 0){
        for(i = 0;i < count;i++){
            struct TreeNode* temp = pop(&enquence);//出队
            sum += temp->val;
            size--;
            if(temp->left != NULL){
                push(&enquence,temp->left);//入队
                nextcount++;
                size++;
            }
            if(temp->right != NULL){
                push(&enquence,temp->right);//入队
                nextcount++;
                size++;
            }
        }
        count = nextcount;
        sumlevel[j] = sum;
        j++;
        nextcount = 0;
        sum = 0;
    }
    //找出最大值的下标
    int max = 0;
    for(i = 1;i < j;i++){
        if(sumlevel[i] > sumlevel[max]){
            max = i;
        }
    }
    return max + 1;
}

此思路时间复杂度较高，但大家如果觉得好的话，就给个免费的赞吧，谢谢了^ _ ^

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

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