[1161. The maximum sum of elements in the layer]

来源：力扣（LeetCode）

描述：

给你一个二叉树的根节点 root.设根节点位于二叉树的第 1 层,而根节点的子节点位于第 2 层,依此类推.

请返回层内元素之和 最大 的那几层（可能只有一层）的层号,并返回其中 最小 的那个.

示例 1：

输入：root = [1,7,0,7,-8,null,null]
输出：2
解释：
第 1 层各元素之和为 1,
第 2 层各元素之和为 7 + 0 = 7,
第 3 层各元素之和为 7 + -8 = -1,
所以我们返回第 2 层的层号,它的层内元素之和最大.

示例 2：

输入：root = [989,null,10250,98693,-89388,null,null,null,-32127]
输出：2

提示：

• 树中的节点数在 [1, 10⁴]范围内
• -10⁵ <= Node.val <= 10⁵

方法一：深度优先搜索

We can traverse this binary tree using a depth-first search,The current layer number is recorded at the same time recursively.

相比哈希表,Here we use a more efficient dynamic array to maintain the sum of the elements of each layer,If the current layer number reaches the length of the array,then add the node element to the end of the array,Otherwise, update the sum of the elements corresponding to the layer number.

然后遍历数组,Find the maximum sum of elements,and the element with the smallest layer number.

代码：

class Solution {
    
    vector<int> sum;

    void dfs(TreeNode *node, int level) {
    
        if (level == sum.size()) {
    
            sum.push_back(node->val);
        } else {
    
            sum[level] += node->val;
        }
        if (node->left) {
    
            dfs(node->left, level + 1);
        }
        if (node->right) {
    
            dfs(node->right, level + 1);
        }
    }

public:
    int maxLevelSum(TreeNode *root) {
    
        dfs(root, 0);
        int ans = 0;
        for (int i = 0; i < sum.size(); ++i) {
    
            if (sum[i] > sum[ans]) {
    
                ans = i;
            }
        }
        return ans + 1; // layer number from 1 开始
    }
};

执行用时：144 ms, 在所有 C++ 提交中击败了94.63%的用户
内存消耗：102.2 MB, 在所有 C++ 提交中击败了97.01%的用户
复杂度分析
时间复杂度： O(n),其中 n 是二叉树的节点个数.
空间复杂度： O(n).The worst case binary tree is a chain,需要 O(n) the array space as well O(n) 的递归栈空间.

方法二：广度优先搜索

Since the calculation is the sum of the elements of each layer,It would be more natural to traverse the tree with a breadth-first search.

For breadth-first search,We can do this with queues.初始时,The queue contains only the root node;然后不断出队,将子节点入队,直到队列为空.

If you directly apply the idea of ​​Method 1,We need to store the node and the layer number of the node in the queue.Another way to do this is to traverse a full layer of nodes at a time,遍历的同时,Accumulates the element-wise sum of the nodes of this layer,At the same time, use the nodes of this layer to get the nodes of the next layer,This practice does not require recording layer numbers.

为了代码实现的方便,We can use two dynamic arrays,第一个数组 q is the node of the current layer,第二个数组 nq is the node of the next layer.遍历 q at the same time as the middle node,Add child nodes to nq 中.After traversing the current layer,将 q 置为 nq.

代码：

class Solution {
    
public:
    int maxLevelSum(TreeNode *root) {
    
        int ans = 1, maxSum = root->val;
        vector<TreeNode*> q = {
    root};
        for (int level = 1; !q.empty(); ++level) {
    
            vector<TreeNode*> nq;
            int sum = 0;
            for (auto node : q) {
    
                sum += node->val;
                if (node->left) {
    
                    nq.emplace_back(node->left);
                }
                if (node->right) {
    
                    nq.emplace_back(node->right);
                }
            }
            if (sum > maxSum) {
    
                maxSum = sum;
                ans = level;
            }
            q = move(nq);
        }
        return ans;
    }
};

执行用时：152 ms, 在所有 C++ 提交中击败了84.78%的用户
内存消耗：109 MB, 在所有 C++ 提交中击败了6.87%的用户
复杂度分析
时间复杂度： O(n),其中 n 是二叉树的节点个数.
空间复杂度： O(n).最坏情况下,数组中有 O(n) 个节点.
author：LeetCode-Solution