[Swift]LeetCode1161.最大层内元素和|MaximumLevelSumofaBinaryTree

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（www.zengqiang.org）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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.

Example 1:

Input: [1,7,0,7,-8,null,null]
Output: 2
Explanation: 
Level 1 sum = 1.
Level 2 sum = 7 + 0 = 7.
Level 3 sum = 7 + -8 = -1.
So we return the level with the maximum sum which is level 2.

Note:

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

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

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

示例：

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

提示：

树中的节点数介于 1 和 10^4 之间
-10^5 <= node.val <= 10^5

740ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     var levels: [Int] = []
16     func maxLevelSum(_ root: TreeNode?) -> Int {
17         traverse(root, 0)
18         var maxValue = root!.val
19         var maxValueIndex = 0
20         for (index, level) in levels.enumerated() {
21             if level > maxValue {
22                 maxValue = level
23                 maxValueIndex = index
24             }
25         }
26         return maxValueIndex + 1
27     }
28     
29     func traverse(_ node: TreeNode?, _ level: Int) {
30         if let node = node {
31             if level >= levels.count {
32                 levels.append(0)
33             }
34             levels[level] += node.val
35             traverse(node.left, level + 1)
36             traverse(node.right, level + 1)
37         }
38     }
39 }

764ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     func maxLevelSum(_ root: TreeNode?) -> Int {
16         var levels: [Int: Int] = [:]
17         dfs(node: root, depth: 1, levels: &levels)
18         var result = 0
19         var maximum = levels[0] ?? Int.min
20         for level in levels {
21             if maximum < (level.value ?? Int.min) {
22                 // new minimum
23                 maximum = (level.value ?? Int.min)
24                 result = level.key
25             }
26         }
27         
28         return result
29     }
30     
31     private func dfs(node: TreeNode?, depth: Int, levels: inout [Int: Int]) {
32         guard let node = node else { return }
33         
34         levels[depth] = (levels[depth] ?? 0) + node.val
35         
36         dfs(node: node.left, depth: depth + 1, levels: &levels)
37         dfs(node: node.right, depth: depth + 1, levels: &levels)
38     }
39 }

808ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15   var maxs = [Int](repeating: 0, count: 10001)
16   func maxLevelSum(_ root: TreeNode?) -> Int {
17     helper(root, 1)
18     return maxs.enumerated().max { (a, b) -> Bool in
19       a.element <= b.element
20     }!.offset
21   }
22   
23   func helper(_ node: TreeNode?, _ lvl: Int) {
24     guard let n = node else {
25       return
26     }
27     maxs[lvl] += n.val
28     helper(n.right, lvl + 1)
29     helper(n.left, lvl + 1)
30   }
31 }

Runtime: 828 ms

Memory Usage: 21 MB

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     var s:[Int:Int] = [Int:Int]()
16     func maxLevelSum(_ root: TreeNode?) -> Int {
17         dfs(root,1)
18         var best:Int = s[1,default:0]
19         var v:Int = 1
20         for (key,val) in s
21         {
22             if val > best
23             {
24                 best = val
25                 v = key
26             }            
27         }
28         return v
29     }
30     
31     func dfs(_ root: TreeNode?,_ level:Int)
32     {
33         if root == nil {return}
34         dfs(root!.left, level + 1)
35         dfs(root!.right, level + 1)
36         s[level,default:0] += root!.val
37     }
38 }