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

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 我的作品

欢迎体验我的作品之一：​​小五笔​​​ 五笔学习好帮手！
​​App Store​​ 搜索即可~