[Swift]LeetCode637.二叉树的层平均值|AverageofLevelsinBinaryTree

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

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

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

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

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

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

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   7
Output: [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 = nil
10  *         self.right = nil
11  *     }
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..<res.count
20         {
21             res[i] /= cnt[i]
22         }
23         return res
24     }
25     
26     func helper(_ node: TreeNode?,_ level:Int,_ cnt:inout [Double],_ res:inout [Double])
27     {
28         if node == nil {return}
29         if res.count <= level
30         {
31             res.append(0)
32             cnt.append(0)            
33         }
34         res[level] += Double(node!.val)
35         cnt[level] += 1
36         helper(node!.left, level + 1, &cnt, &res)
37         helper(node!.right,level + 1, &cnt, &res)
38     }
39 }

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 = nil
10  *         self.right = nil
11  *     }
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.0
25         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 = arrNext
44                 arrNext.removeAll()
45                 curSum = 0
46             }
47         }
48 
49         return ans
50     }
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 = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     func averageOfLevels(_ root: TreeNode?) -> [Double] {
16         var stack = [TreeNode?]()
17         stack.append(root)
18         var sum = 0.0
19         var ans = [Double]()
20         var counter = 0.0
21         while stack.count > 0 {
22             let size = stack.count
23             var tempStack = [TreeNode?]()
24             sum = 0.0
25             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 ans
40     }
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 = 0
13         var count = 0
14         
15         
16         while queue.count > 0 {
17             count = queue.count
18             
19             for _ in 0..<queue.count {
20                 let node = pop()
21                 sum = sum + node.val
22                 if let left = node.left {
23                     push(node: left)
24                 }
25                 if let right = node.right {
26                     push(node: right)
27                 }
28             }
29             avg.append(Double(sum)/Double(count))
30             sum = 0
31             
32         }
33         
34         return avg
35         
36     }
37     
38     
39     func pop() -> 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 = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 
15 public struct Queue<T> {
16     fileprivate var array = [T?]()
17     fileprivate var head = 0
18     
19     public var isEmpty: Bool {
20         return count == 0
21     }
22     
23     public var count: Int {
24         return array.count - head
25     }
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] = nil
35         head += 1
36         
37         let percentage = Double(head)/Double(array.count)
38         if array.count > 50 && percentage > 0.25 {
39             array.removeFirst(head)
40             head = 0
41         }
42         
43         return element
44     }
45     
46     public var front: T? {
47         if isEmpty {
48             return nil
49         } 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 = 0
61         
62         if let current_node = root {
63             frontier.enqueue((current_node, currentLevel))
64         } else {
65             return avgs
66         }
67         
68         var levelSum = 0.0
69         var levelCount = 0.0
70         while true {
71             if frontier.isEmpty {
72                 break
73             }
74             let newItem = frontier.dequeue()
75             let newNode = newItem?.0
76             let newLevel = newItem?.1
77             if (newLevel != currentLevel) {
78                 avgs.append(levelSum / levelCount)
79                 currentLevel = newLevel!
80                 levelSum = 0
81                 levelCount = 0
82             }
83             
84             levelCount += 1
85             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 avgs
96     }
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 = nil
10  *         self.right = nil
11  *     }
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] = value
28         } 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 = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 
15 enum QueueElement {
16     case node(TreeNode)
17     case line
18 }
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 = 0
29         var sum: Double = 0
30         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 += 1
38                 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 = 0
54                 sum = 0
55             }
56         }
57         
58         return result
59     }
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..<count {
            node = tree.removeFirst()
            level += Double(node.val)
            if let left = node.left {
                tree.append(left)
            }
            if let right = node.right {
                tree.append(right)
            }
        }
        res.append(level / Double(count))
    }
    return res
  }
}

116ms

 1 class Solution {
 2 
 3 func averageOfLevels(_ root: TreeNode?) -> [Double]
 4 {
 5     guard let root = root else { return [] }
 6     var dict = Dictionary<Int, [Double]>()
 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 = 0
14         for n in dict[key]!
15         {
16             sum += n
17         }
18         results.append(sum/Double(dict[key]!.count))
19     }
20     return results
21 }
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?.val
28     {
29         if let _ = dict[rows]
30         {
31             dict[rows]?.append(Double(left))
32         }
33         else
34         {
35             dict[rows] = [Double(left)]
36         }
37     }
38     
39     if let right = root.right?.val
40     {
41         if let _ = dict[rows]
42         {
43             dict[rows]?.append(Double(right))
44         }
45         else
46         {
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 = 0
10             let count = tmp.count
11             var sum: Double = 0
12 
13             while index < count {
14                 sum += Double(tmp[index].val)
15 
16