二叉树中任意两个层级和的最大绝对差

---

在这个问题中，我们将找到任意两个层级的所有节点之和之间的最大绝对差。

我们可以使用队列数据结构遍历每个二叉树层级。在遍历每个层级时，我们可以跟踪最大和最小和，并在最后返回绝对差。

问题陈述 - 我们给定一个包含正整数和负整数的二叉树。我们需要找到任意两个层级的所有节点之和的最大绝对差。

示例

输入

                  
                  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 和层序遍历来遍历每个层级并获取每个层级的总和。