二叉樹中任意兩個層級和的最大絕對差

---

在這個問題中，我們將找到任意兩個層級的所有節點之和之間的最大絕對差。

我們可以使用佇列資料結構遍歷每個二叉樹層級。在遍歷每個層級時，我們可以跟蹤最大和最小和，並在最後返回絕對差。

問題陳述 - 我們給定一個包含正整數和負整數的二叉樹。我們需要找到任意兩個層級的所有節點之和的最大絕對差。

示例

輸入

                  
                  300
	            /     \
	           5       7
 	         /   \     /
	        1     1    1

輸出

297

解釋 - 第一層的節點之和為 300，最後一層的節點之和為 3。因此，最大差值為 297。

輸入

                   
                       10
	              /  \
	             -9  -8
 	             / \  /
	           10   6 11

輸出

44

解釋 - 最後一層的節點之和為 27，第二層的節點之和為 -17。因此，絕對差值為 27 - (-17) 為 44。

輸入

                  
                  -50
	             /   \
	            19   -21
 	           /  \  /  \
	         -12   9 21  -20

輸出

48

解釋 - 第一層的節點之和為 -50，第二層的節點之和為 -2。因此，-50 - (-2) 為 48。

方法

在這種方法中，我們將使用層序遍歷。在遍歷每個層級時，我們將計算每個層級所有節點的總和。此外，我們將儲存最大和最小層級總和。最後，我們將取其絕對差並將其作為答案返回。

演算法

步驟 1 - 定義 TreeNode 類以建立二叉樹的節點。TreeNode 類包含 'val' 整數值、'left' 和 'right' 指標。此外，它包含一個建構函式來初始化二叉樹的新節點。

步驟 2 - 現在，定義 max_sum 並初始化為最小整數值以儲存最大和。此外，定義 min_sum 並將其初始化為最大整數值以儲存最小和。

步驟 3 - 定義佇列並將樹的根節點插入佇列。

步驟 4 - 使用 while 迴圈並進行迭代，直到佇列至少包含一個節點。

步驟 4.1 - 將 'sum' 初始化為 0 以儲存當前層級的總和。

步驟 4.2 - 使用巢狀 for 迴圈開始遍歷佇列元素。

步驟 4.2.1 - 彈出第一個佇列元素，並將它的值新增到 sum 變數。

步驟 4.2.2 - 如果 'temp' 的左節點不為空，則將其插入佇列。同樣，如果 'temp' 的右節點不為空，則將其插入佇列。

步驟 4.3 - 如果當前和大於 max_sum 或小於 min_sum，則更新 max_sum 和 min_sum 值。

步驟 5 - 最後，返回 max_sum 和 min_sum 之間的絕對差。

示例

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

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int val) {
        this->val = val;
        left = NULL;
        right = NULL;
    }
};
int maxAbsDiff(TreeNode *head) {
    int max_sum = INT_MIN;
    int min_sum = INT_MAX;
    queue<TreeNode *> que;
    que.push(head);
    // BFS
    while (!que.empty()) {
        int temp_size = que.size();
        // Initial sum is 0.
        int sum = 0;
        for (int p = 0; p < temp_size; p++) {
            TreeNode *temp = que.front();
            que.pop();
            // Add value to the sum
            sum += temp->val;
            // Insert the left and right node of the current node to queue
            if (temp->left != NULL)
                que.push(temp->left);

            if (temp->right != NULL)
                que.push(temp->right);
        }
        max_sum = max(max_sum, sum);
        min_sum = min(min_sum, sum);
    }
    // Get difference
    return abs(max_sum - min_sum);
}
int main() {
    TreeNode *head = new TreeNode(300);
    head->left = new TreeNode(5);
    head->right = new TreeNode(7);
    head->left->left = new TreeNode(1);
    head->left->right = new TreeNode(1);
    head->right->left = new TreeNode(1);
    cout << "The maximum absolute difference between the sum of two levels of binary tree is " << maxAbsDiff(head) << endl;
}

輸出

The maximum absolute difference between the sum of two levels of binary tree is 297

時間複雜度 - O(N) 以訪問所有節點。

空間複雜度 - O(N) 以在佇列中儲存節點。

我們使用 BFS 和層序遍歷來遍歷每個層級並獲取每個層級的總和。