1161.md

Maximum Level Sum of a Binary Tree

题目

Given the root of a binary tree, the level of its root is 1, the level of its children is 2, and so on.

Return the smallest level X such that the sum of all the values of nodes at level X is maximal.

Note:

The number of nodes in the given tree is between 1 and 10^4. -10^5 <= node.val <= 10^5

找出树中层的和的最大值的 层。如果有相同层级都是最大值，则返回最小层。

思路

总结：
	tree, dfs. 使用一个map记录每一层的sum值。最后找出map中的最大值的level。

代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxLevelSum(root *TreeNode) int {
    maxSum, maxLevel := math.MinInt64, 0
    levelSum := make(map[int]int, 0)
    dfs(root, 1, &levelSum)
    for k, v := range levelSum {
        if v > maxSum {
            maxLevel, maxSum = k, v
        }
    }
    return maxLevel
}

func dfs(node *TreeNode, level int, levelSum *map[int]int) {
    if node == nil {
        return
    }
    (*levelSum)[level] += node.Val
    dfs(node.Left, level+1, levelSum)
    dfs(node.Right, level+1, levelSum)    
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxLevelSum(root *TreeNode) int {
    if root == nil {
        return 0
    }
    max := ^(int(^uint(0) >> 1))
    ptrSlice := []*TreeNode{root}
    curSum, maxLevel, curLevel :=  0, 1, 1
    for len(ptrSlice) != 0 {
        curSum = 0
        tmpSlice := make([]*TreeNode, 0)
        //fmt.Println(end)
        for index := 0; index < len(ptrSlice); index++ {
            curSum += ptrSlice[index].Val
            if ptrSlice[index].Left!=nil {
                tmpSlice = append(tmpSlice, ptrSlice[index].Left)
            }
            if ptrSlice[index].Right!=nil {
                tmpSlice = append(tmpSlice, ptrSlice[index].Right)
            }
        }
        if curSum > max {
            max, maxLevel = curSum, curLevel
        }
        curLevel++
        ptrSlice = tmpSlice
    }
    return maxLevel
}