题目

题目来源：力扣（LeetCode）

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

请你找出层内元素之和 最大 的那几层（可能只有一层）的层号，并返回其中 最小 的那个。

示例 1：
image.png
输入：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. 递归实现的中序遍历非常简单：遵循 Left->Node->Right 的顺序。例如：首先递归访问 左孩子， 然后访问父节点，再递归访问 右孩子。
  2. 遍历时需要记录当前层节点之和。
  3. 创建方法 inorder(node, level)，实现递归的中序遍历。该方法输入当前节点和当前节点层级，然后递归更新 nodesArr[level]。
  4. 计算每层元素之和，返回符合要求的层级
  1. /**
  2.  * Definition for a binary tree node.
  3.  * function TreeNode(val, left, right) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.left = (left===undefined ? null : left)
  6.  *     this.right = (right===undefined ? null : right)
  7.  * }
  8.  */
  9. /**
  10.  * @param {TreeNode} root
  11.  * @return {number}
  12.  */
  13. var maxLevelSum = function (root) {
  14.   // 二维数组，存储每层的节点
  15.   let nodesArr = []
  16.   // 递归实现的中序遍历
  17.   // 参数为 当前节点和当前节点层级
  18.   function inorder(node, level) {
  19.     if (!node) return
  20.     nodesArr[level] = nodesArr[level] || []
  21.     nodesArr[level].push(node.val)
  22.     inorder(node.left, level + 1)
  23.     inorder(node.right, level + 1)
  24.   }
  26.   inorder(root, 0)
  28.   let ans = []
  29.   // 计算每层的节点之和
  30.   for (let i = 0; i < nodesArr.length; i++) {
  31.     sum = nodesArr[i].reduce((sum, cur) => sum + cur)
  32.     ans.push(sum)
  33.   }
  34.   // 层内元素之和最大值
  35.   let max = Math.max(...ans)
  36.   // 返回层级
  37.   return ans.indexOf(max) + 1
  38. };