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。求奇數層和偶數層節點之和的絕對差值。

示例 1

輸入

        10          -> Level 0
     /   |   \
   -5   20    15    -> Level 1
   / \      / |   \
 -10  -3  0  8   -7 -> Level 2

輸出

32

解釋

• 偶數層節點之和 = 10 + (-10) + (-3) + 0 + 8 + (-7) = -2

• 奇數層節點之和 = (-5) + 20 + 15 = 30

• 絕對差值 = |30 - (-2)| = 32

示例 2

輸入

        50                    -> Level 0
     /   |   \
   25   -30   45              -> Level 1
   / \        / |   \
 -15  10    20  5    35       -> Level 2
  / \               / |   \
-20 -10           15  40  -5  -> Level 3

輸出

45

解釋

• 偶數層節點之和 = 50 + (-15) + 10 + 20 + 5 + 35 = 105

• 奇數層節點之和 = 25 + (-30) + 45 + (-20) + (-10) + 15 + 40 + (-5) = 60

• 絕對差值 = |60 - 105| = 45

解決方案：層序遍歷

這個問題可以透過對樹進行層序遍歷來解決，分別儲存奇數層和偶數層的和，最後求它們的絕對差值。

虛擬碼

function evenOddDiff(root: Node) -> integer
   even <- 0
   odd <- 0
   queue <- new Queue of (Node, integer) pairs
   queue.push((root, 0))

   while queue is not empty
      curr, level <- queue.pop()
      data <- curr.val

      if level is even
          even <- even + data
      else
         odd <- odd + data

      for c in curr.child
         queue.push((c, level + 1))

   return abs(odd - even)

示例：C++ 實現

下面的程式對 N叉樹進行層序遍歷，以獲得 N叉樹中奇數層和偶數層之和的差值。

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

// Structure of node in the N-ary tree
struct Node {
   int val;
   vector<Node *> child;
};
// Creating a new node in the N-ary tree
Node *newNode(int val) {
   Node *temp = new Node;
   temp->val = val;
   return temp;
}
// Function to find the difference bewtween the odd and even level sum of nodes in the N-ary tree
int evenOddDiff(Node *root) {
   int even = 0, odd = 0;
   // Queue of pair storing node value and level
   queue<pair<Node *, int>> q;
   q.push({root, 0});
   while (!q.empty()) {
      pair<Node *, int> curr = q.front();
      q.pop();
      int level = curr.second;
      int data = curr.first->val;
      // Checking level and adding the value of node to sum
      if (level % 2)
      odd += data;
      else
      even += data;
      // Adding new nodes to queue along with updated level
      for (auto c : curr.first->child) {
         q.push({c, level + 1});
      }
   }
   return abs(odd - even);
}
int main(){
   Node *root = newNode(50);
   root->child.push_back(newNode(25));
   root->child.push_back(newNode(-30));
   root->child.push_back(newNode(45));
   root->child[0]->child.push_back(newNode(-15));
   root->child[0]->child.push_back(newNode(10));
   root->child[2]->child.push_back(newNode(20));
   root->child[2]->child.push_back(newNode(5));
   root->child[2]->child.push_back(newNode(35));
   root->child[0]->child[0]->child.push_back(newNode(-20));
   root->child[0]->child[0]->child.push_back(newNode(-10));
   root->child[2]->child[2]->child.push_back(newNode(15));
   root->child[2]->child[2]->child.push_back(newNode(40));
   root->child[2]->child[2]->child.push_back(newNode(-5));
   cout << evenOddDiff(root);
   return 0;
}

輸出

45

時間複雜度 − O(N)，因為在遍歷 N叉樹時，我們遍歷了樹的所有節點。

空間複雜度 − O(N)，因為樹的所有節點都儲存在使用的佇列資料結構中。

結論

總之，提供的解決方案有助於找到 N叉樹中奇數層和偶數層之和的絕對差值。程式碼的時間和空間複雜度均為 O(N)，其中 N 是 N叉樹中節點的總數。使用廣度優先搜尋或層序遍歷，我們同時計算了 N叉樹奇數層和偶數層的和。絕對差值是透過減去這兩個計算出的和得到的。