★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）➤博客园地址：山青咏芝（）➤GitHub地址：➤原文地址： ➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.
Example 1:
Input: 3 / \ 9 20 / \ 15 7Output: [3, 14.5, 11]Explanation:The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].
Note:
- The range of node's value is in the range of 32-bit signed integer.
给定一个非空二叉树, 返回一个由每层节点平均值组成的数组.
示例 1:
输入: 3 / \ 9 20 / \ 15 7输出: [3, 14.5, 11]解释:第0层的平均值是 3, 第1层是 14.5, 第2层是 11. 因此返回 [3, 14.5, 11].
注意：
- 节点值的范围在32位有符号整数范围内。
Runtime: 60 ms
Memory Usage: 20.7 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 = nil10 * self.right = nil11 * }12 * }13 */14 class Solution {15 func averageOfLevels(_ root: TreeNode?) -> [Double] {16 var res:[Double] = [Double]()17 var cnt:[Double] = [Double]()18 helper(root, 0, &cnt, &res)19 for i in 0.. 72ms
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 = nil10 * self.right = nil11 * }12 * }13 */14 class Solution {15 func averageOfLevels(_ root: TreeNode?) -> [Double] {16 if root == nil {17 return [0]18 }19 20 var arrCur = [TreeNode]()21 arrCur.append(root!)22 var arrNext = [TreeNode]()23 24 var curSum = 0.025 var ans = [Double]()26 ans.append(Double(root!.val))27 while arrCur.count > 0 {28 let node = arrCur.remove(at: 0)29 if node.left != nil {30 arrNext.append(node.left!)31 curSum += Double(node.left!.val)32 }33 34 if node.right != nil {35 arrNext.append(node.right!)36 curSum += Double(node.right!.val)37 }38 39 if arrCur.count == 0 {40 if arrNext.count > 0 {41 ans.append(curSum/Double(arrNext.count))42 }43 arrCur = arrNext44 arrNext.removeAll()45 curSum = 046 }47 }48 49 return ans50 }51 } 76ms
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 = nil10 * self.right = nil11 * }12 * }13 */14 class Solution {15 func averageOfLevels(_ root: TreeNode?) -> [Double] {16 var stack = [TreeNode?]()17 stack.append(root)18 var sum = 0.019 var ans = [Double]()20 var counter = 0.021 while stack.count > 0 {22 let size = stack.count23 var tempStack = [TreeNode?]()24 sum = 0.025 for i in stride(from: size - 1, to: -1, by: -1) {26 let node = stack[i]!27 sum += Double(node.val)28 if let left = node.left {29 tempStack.append(left)30 }31 if let right = node.right {32 tempStack.append(right)33 }34 }35 stack.removeAll()36 ans.append(sum / Double(size))37 stack.append(contentsOf: tempStack)38 } 39 return ans40 }41 } 80ms
1 class Solution { 2 var queue: [TreeNode] = [] 3 4 func averageOfLevels(_ root: TreeNode?) -> [Double] { 5 var avg: [Double] = [] 6 7 guard let root = root else { 8 return avg 9 }10 11 push(node: root)12 var sum = 013 var count = 014 15 16 while queue.count > 0 {17 count = queue.count18 19 for _ in 0.. TreeNode {40 return queue.removeFirst()41 }42 43 func push(node: TreeNode) {44 queue.append(node)45 }46 } 84ms
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 = nil10 * self.right = nil11 * }12 * }13 */14 15 public struct Queue {16 fileprivate var array = [T?]()17 fileprivate var head = 018 19 public var isEmpty: Bool {20 return count == 021 }22 23 public var count: Int {24 return array.count - head25 }26 27 public mutating func enqueue(_ element: T) {28 array.append(element)29 }30 31 public mutating func dequeue() -> T? {32 guard head < array.count, let element = array[head] else { return nil }33 34 array[head] = nil35 head += 136 37 let percentage = Double(head)/Double(array.count)38 if array.count > 50 && percentage > 0.25 {39 array.removeFirst(head)40 head = 041 }42 43 return element44 }45 46 public var front: T? {47 if isEmpty {48 return nil49 } else {50 return array[head]51 }52 }53 }54 55 56 class Solution {57 func averageOfLevels(_ root: TreeNode?) -> [Double] {58 var avgs: [Double] = []59 var frontier = Queue<(TreeNode, Int)>()60 var currentLevel = 061 62 if let current_node = root {63 frontier.enqueue((current_node, currentLevel))64 } else {65 return avgs66 }67 68 var levelSum = 0.069 var levelCount = 0.070 while true {71 if frontier.isEmpty {72 break73 }74 let newItem = frontier.dequeue()75 let newNode = newItem?.076 let newLevel = newItem?.177 if (newLevel != currentLevel) {78 avgs.append(levelSum / levelCount)79 currentLevel = newLevel!80 levelSum = 081 levelCount = 082 }83 84 levelCount += 185 levelSum += Double(newNode!.val)86 87 if let leftChild = newNode?.left {88 frontier.enqueue((leftChild, currentLevel + 1))89 }90 if let rightChild = newNode?.right {91 frontier.enqueue((rightChild, currentLevel + 1))92 }93 }94 avgs.append(levelSum / levelCount)95 return avgs96 }97 } 88ms
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 = nil10 * self.right = nil11 * }12 * }13 */14 class Solution {15 func averageOfLevels(_ root: TreeNode?) -> [Double] {16 guard let root = root else { return [] }17 18 var solution = [[Double]]()19 _averageOfLevels(root, &solution, 0)20 return solution.map { $0.reduce(0,+) / Double($0.count) }21 }22 23 func _averageOfLevels(_ root: TreeNode, _ solution: inout [[Double]], _ level: Int) {24 if solution.indices.contains(level) {25 var value = solution[level]26 value.append(Double(root.val))27 solution[level] = value28 } else {29 solution.append([Double(root.val)])30 }31 32 if let left = root.left { _averageOfLevels(left, &solution, level + 1) }33 if let right = root.right { _averageOfLevels(right, &solution, level + 1) }34 }35 } 92ms
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 = nil10 * self.right = nil11 * }12 * }13 */14 15 enum QueueElement {16 case node(TreeNode)17 case line18 }19 20 class Solution {21 func averageOfLevels(_ root: TreeNode?) -> [Double] {22 guard let rootNode = root else {23 return []24 }25 26 var result = [Double]()27 28 var lineNodeCount = 029 var sum: Double = 030 var queue = [QueueElement]()31 queue.append(.node(rootNode))32 queue.append(.line)33 while !queue.isEmpty {34 let ele = queue.removeFirst()35 switch ele {36 case let .node(n):37 lineNodeCount += 138 sum += Double(n.val)39 40 if n.left != nil {41 queue.append(.node(n.left!))42 }43 44 if n.right != nil {45 queue.append(.node(n.right!))46 }47 case .line:48 if lineNodeCount > 0 {49 result.append(sum / Double(lineNodeCount))50 queue.append(.line)51 }52 53 lineNodeCount = 054 sum = 055 }56 }57 58 return result59 }60 } 100ms
/** * Definition for a binary tree node. * public class TreeNode { * public var val: Int * public var left: TreeNode? * public var right: TreeNode? * public init(_ val: Int) { * self.val = val * self.left = nil * self.right = nil * } * } */class Solution {func averageOfLevels(_ root: TreeNode?) -> [Double] { var tree = [TreeNode]() var res = [Double]() guard let root = root else { return res } tree.append(root) var node = root while !tree.isEmpty { var level = 0.0 let count = tree.count for _ in 0.. 116ms
1 class Solution { 2 3 func averageOfLevels(_ root: TreeNode?) -> [Double] 4 { 5 guard let root = root else { return [] } 6 var dict = Dictionary () 7 dict[0] = [Double(root.val)] 8 getDict(root, 1, &dict) 9 10 var results = [Double]()11 for key in dict.keys.sorted(by: <)12 {13 var sum: Double = 014 for n in dict[key]!15 {16 sum += n17 }18 results.append(sum/Double(dict[key]!.count))19 }20 return results21 }22 23 func getDict(_ root: TreeNode?, _ rows: Int, _ dict: inout [Int : [Double]])24 {25 guard let root = root else { return }26 27 if let left = root.left?.val28 {29 if let _ = dict[rows]30 {31 dict[rows]?.append(Double(left))32 }33 else34 {35 dict[rows] = [Double(left)]36 }37 }38 39 if let right = root.right?.val40 {41 if let _ = dict[rows]42 {43 dict[rows]?.append(Double(right))44 }45 else46 {47 dict[rows] = [Double(right)]48 }49 }50 getDict(root.left, rows+1, &dict)51 getDict(root.right, rows+1, &dict)52 }53 } 156ms
1 class Solution { 2 func averageOfLevels(_ root: TreeNode?) -> [Double] { 3 var result: [Double] = [] 4 var tmp: [TreeNode] = [] 5 var level = 0 6 7 tmp.append(root!) 8 while tmp.count != 0 { 9 var index = 010 let count = tmp.count11 var sum: Double = 012 13 while index < count {14 sum += Double(tmp[index].val)15 16 if tmp[index].left != nil {17 tmp.append(tmp[index].left!)18 }19 if tmp[index].right != nil {20 tmp.append(tmp[index].right!)21 }22 index += 123 }24 25 tmp.removeSubrange(tmp.startIndex.. 172ms
1 class Solution { 2 func averageOfLevels(_ root: TreeNode?) -> [Double] 3 { 4 var dic:Dictionary = Dictionary.init() 5 averageOfLevelsWithDic(&dic, root: root, level: 0) 6 7 let result3 = dic.sorted { (str1, str2) -> Bool in 8 return str1.0 < str2.0 9 }10 11 var arr:[Double] = []12 for value in result3 {13 arr.append(Double(value.value.reduce(0, +))/Double(value.value.count))14 } 15 return arr16 }17 18 19 func averageOfLevelsWithDic(_ dic:inout Dictionary , root: TreeNode?,level:Int){20 if root != nil {21 var arr = dic[level]22 if arr == nil{23 arr = []24 }25 arr!.append(root!.val)26 dic[level] = arr27 averageOfLevelsWithDic(&dic, root: root?.left, level: level+1)28 averageOfLevelsWithDic(&dic, root: root?.right, level: level+1)29 }30 }31 }