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;
}

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

相关推荐

  1. LeetCode 2656.K个元素

    2024-07-22 00:56:01       60 阅读
  2. Leetcode.2862 完全子集的元素

    2024-07-22 00:56:01       39 阅读
  3. leetcode 1191.k次串联后子数组之和

    2024-07-22 00:56:01       49 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-22 00:56:01       171 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-22 00:56:01       189 阅读
  3. 在Django里面运行非项目文件

    2024-07-22 00:56:01       157 阅读
  4. Python语言-面向对象

    2024-07-22 00:56:01       170 阅读

热门阅读

  1. 【Node.js基础04】node.js模块化

    2024-07-22 00:56:01       36 阅读
  2. Postman实战案例:从零开始设计API测试流程

    2024-07-22 00:56:01       39 阅读
  3. linux文本查看命令

    2024-07-22 00:56:01       31 阅读
  4. 基于深度学习的医学影像分类

    2024-07-22 00:56:01       38 阅读
  5. 装修前需要提前准备啥

    2024-07-22 00:56:01       29 阅读
  6. 数组指针跟指针数组的区别

    2024-07-22 00:56:01       30 阅读
  7. OpenWRT/iStoreOS 安装 qemu-guest-agent

    2024-07-22 00:56:01       42 阅读
  8. 计算机学院——秋招的总结

    2024-07-22 00:56:01       42 阅读
  9. go中map

    go中map

    2024-07-22 00:56:01      43 阅读