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叉樹進行層序遍歷以獲取最大層級和。

#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

結論

總之，N叉樹是一種樹形資料結構，其中每個節點最多可以有N個子節點。給定的C++程式碼展示瞭如何在N叉樹中找到最大層級和。它使用鄰接表表示樹，並使用佇列執行層序遍歷。最大層級和會被更新，最終結果以O(N)的時間複雜度返回。