【二叉树】最大层内元素和

0x00 题目

给你一个二叉树的根节点 ​

​root​

​​ 设根节点位于二叉树的第 ​

​1​

​ 层

而根节点的子节点位于第 ​

​2​

​ 层

依此类推

请返回层内元素之和

​​

​最大​

​​ 的那几层（可能只有一层）的层号

并返回其中 ​​

​最小​

​ 的那个

0x01 思路

要求出​

​层​

​​内元素之和

就需要使用​​

​层序​

​​遍历方式

记录一个​​

​最大​

​​值并进行比较

同时记录最大值所在的​​

​层数​

​即可

0x02 解法

语言：​

​Swift​

​

树节点：​

​TreeNode​

​

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}      

func maxLevelSum(_ root: TreeNode?) -> Int {
    guard let root = root else { return 0 }

    var res = root.val
    var cur = 1
    var floor = 1
    var queue: [TreeNode?] = []
    queue.append(root)

    while !queue.isEmpty {
        var temp: [TreeNode?] = []
        // 层元素和
        var val = Int.min

        while !queue.isEmpty {
            let node = queue.removeFirst()
            if let left = node?.left {
                temp.append(left)
                val += left.val
            }
            if let right = node?.right {
                temp.append(right)
                val += right.val
            }

        }

        // 为空，跳出
        if temp.isEmpty {
           break
        }
        
        // 小于则更新
        if res < val {
            res = val
            floor = cur
        }
        cur += 1
        queue = temp
    }

    return floor
}
      

0x03 我的作品