N叉树中最大层级和

N叉树是一种树形数据结构，其中每个节点最多可以有N个子节点，其中N是一个正整数（N >= 0）。N叉树在许多应用中使用，例如文件系统、组织结构图和编程语言中的语法树。

N=4的N叉树示例。

          A
      /  /  \  \
     B   C   D   E
   / | \     |   | \
  F  G  H    I   J  K
        |    |
        L    M

问题陈述

给定一棵具有N个节点的树，节点编号从0到N-1，以及一个包含每个节点值的数组A[]，即A[i]表示第i个节点的值。节点之间的关系由一个二维数组edges[][]给出。任务是找到树的最大层级和。

示例1

输入

N = 8
A[] = {1, 7, 8, 9, 5, 2, 3, 4}
edges[][] = {{0, 1}, {0, 2}, {0, 3}, {2, 4}, {3, 5}, {5, 6}, {5, 7}}

输出

24

解释

  • 第0层的和：1

  • 第1层的和：7+8+9 = 24

  • 第2层的和：5+2 = 7

  • 第3层的和：3+4 = 7

  • 最大和为24，即第1层。

示例2

输入

N = 3
A[] = {1, 3, 2}
edges[][] = {{0, 1}, {1, 2}}

输出

3

解释

  • 第0层的和：1

  • 第1层的和：3

  • 第2层的和：1

  • 最大和为3，即第1层。

解决方案方法

可以通过对树进行层序遍历，并存储每一层的和，最后选择最大和并确定具有最大和的层级来解决该问题。

伪代码

function maximumLevelSum(N, edges, A):
   adj[N]
   for i from 0 to (N - 1):
      adj[edges[i][0]].push_back(edges[i][1])
   maxLevelSum = A[0]
   queue q
   q.push(0)
   while q is not empty:
      count = q.size()
      sum = 0
      while count > 0:
         node = q.front()
         q.pop()
         sum += A[node]
         for i from 0 to size of adj[node]:
            q.push(adj[node][i])
         count = count - 1
      maxLevelSum = max(maxLevelSum, sum)
   return maxLevelSum

示例：C++实现

以下程序对N叉树进行层序遍历以获取最大层级和。

Open Compiler
#include <bits/stdc++.h>
using namespace std;

// Function to find the maximum level sum in N-ary tree
int maximumLevelSum(int N, int edges[][2], vector<int> A){
   // Creating the adjacency list representation for the tree
   vector<int> adj[N];
   for (int i = 0; i < (N - 1); i++){
      adj[edges[i][0]].push_back(edges[i][1]);
   }
   // Initialize the maximum level sum as the val[0] which is the level sum for level 0
   int maxLevelSum = A[0];
   // Creating a queue to store the nodes of each level for performing the level order traversal
   queue<int> q;
   q.push(0);
   // level order traversal
   while (!q.empty()){
      int count = q.size();
      int sum = 0;
      while (count--) {
         int node = q.front();
         q.pop();
         sum += A[node];
         for (int i = 0; i < adj[node].size(); i++) {
            q.push(adj[node][i]);
         }
      }
      // Update maximum level sum
      maxLevelSum = max(maxLevelSum, sum);
   }
   // Return the maximum level order sum
   return maxLevelSum;
}
int main(){
   int N = 8;
   int edges[][2] = {{0, 1}, {0, 2}, {0, 3}, {2, 4}, {3, 5}, {5, 6}, {5, 7}};
   vector<int> A = {1, 7, 8, 9, 5, 2, 3, 4};
   cout << maximumLevelSum(N, edges, A);
   return 0;
}

输出

24

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

结论

总之，N叉树是一种树形数据结构，其中每个节点最多可以有N个子节点。给定的C++代码展示了如何在N叉树中找到最大层级和。它使用邻接表表示树，并使用队列执行层序遍历。最大层级和会被更新，最终结果以O(N)的时间复杂度返回。

更新于： 2023年11月3日

322 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告