C++ 二叉树中任意两层节点之和的最大绝对差

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

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

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

示例

输入

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’的右节点不为空，则将其插入队列。

步骤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和层次遍历来遍历每个层级并得到每个层级的总和。