[Swift]LeetCode515.在每个树行中找最大值|FindLargestValueinEachTreeRow

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

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

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

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

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

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

You need to find the largest value in each row of a binary tree.

Example:

Input: 

          1
         / \
        3   2
       / \   \  
      5   3   9 

Output: [1, 3, 9]

您需要在二叉树的每一行中找到最大的值。

示例：

输入: 

          1
         / \
        3   2
       / \   \  
      5   3   9 

输出: [1, 3, 9]

48ms

 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 largestValues(_ root: TreeNode?) -> [Int] {
16         guard let rootNode = root else {
17             return []
18         }
19         var result: [Int] = []
20         var originallist: [TreeNode] = [rootNode]
21         
22         while !originallist.isEmpty {
23             var tempList: [TreeNode] = originallist
24             originallist.removeAll()
25             var tempvalue: Int = Int.min
26             for var node: TreeNode in tempList {
27                 tempvalue = max(tempvalue,node.val)
28                 if let left: TreeNode = node.left {
29                     originallist.append(left)
30                 }
31                 if let right: TreeNode = node.right {
32                     originallist.append(right)
33                 }
34             }
35             result.append(tempvalue)
36         }
37         return  result        
38     }
39 }

56ms

 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 largestValues(_ root: TreeNode?) -> [Int] {
16         guard let root = root else {
17             return []
18         }
19         var maxVals: [Int] = [root.val]
20         getMaxValues(root, 0, &maxVals)
21         return maxVals
22     }
23     
24     func getMaxValues(_ root: TreeNode, _ currentLevel: Int, _ maxVals: inout [Int]) {
25         if maxVals.count > currentLevel {
26             if root.val > maxVals[currentLevel] {
27                 maxVals[currentLevel] = root.val
28             }
29         } else {
30             maxVals.append(root.val)
31         }
32         
33         if let left = root.left {
34             getMaxValues(left, currentLevel + 1, &maxVals)
35         }
36         if let right = root.right {
37             getMaxValues(right, currentLevel + 1, &maxVals)
38         }
39     }
40 }

Runtime: 60 ms

Memory Usage: 20.3 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 largestValues(_ root: TreeNode?) -> [Int] {
16         if root == nil {return []}
17         var res:[Int] = [Int]()
18         helper(root,1,&res)
19         return res
20     }
21     
22     func helper(_ root: TreeNode?,_ depth:Int,_ res:inout [Int])
23     {
24         if depth > res.count {res.append(root!.val)}
25         else {res[depth - 1] = max(res[depth - 1], root!.val)}
26         if root!.left != nil {helper(root!.left, depth + 1, &res)}
27         if root!.right != nil {helper(root!.right, depth + 1, &res)}
28     }
29 }

68ms

 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 largestValues(_ root: TreeNode?) -> [Int] {
16         if root == nil {
17             return []
18         }
19         var maxVal = Int.min
20         var maxArray = [Int]()
21         var queue = [TreeNode?]()
22         queue.append(root)
23         queue.append(nil)
24         
25         while !queue.isEmpty {
26             var node = queue.removeFirst()
27             if node == nil {
28                 maxArray.append(maxVal)
29                 maxVal = Int.min
30                 if !queue.isEmpty {
31                     queue.append(nil)
32                 }
33             } else {
34                 maxVal = max(maxVal, node?.val ?? 0)
35                 if node?.left != nil {
36                     queue.append(node?.left)
37                 }
38             
39                 if node?.right != nil {
40                     queue.append(node?.right)
41                 }
42             }
43         }
44         return maxArray
45     }
46 }

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 largestValues(_ root: TreeNode?) -> [Int] {
16         guard let root = root else { return [] }
17         var queue = [TreeNode]()
18         queue.append(root)
19         var result = [root.val]
20         while !queue.isEmpty {
21             var maximum = Int.min
22             var tmpQueue = [TreeNode]()
23             while !queue.isEmpty {
24                 let node = queue[0]
25                 queue.removeFirst()
26                 if let left = node.left {
27                     tmpQueue.append(left)
28                     maximum = max(maximum, left.val)
29                 }
30                 if let right = node.right {
31                     tmpQueue.append(right)
32                     maximum = max(maximum, right.val)
33                 }
34 
35             }
36             if !tmpQueue.isEmpty {
37                 result.append(maximum)
38             }
39             queue = tmpQueue
40         }
41         return result
42     }
43 }

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 largestValues(_ root: TreeNode?) -> [Int] {        
16         var q = [TreeNode?]()
17         var remainingNodesInLevel = 0
18         var maxNums = [Int]()    
19         q.append(root)        
20         while q.count > 0 {            
21             remainingNodesInLevel = q.count            
22             var levelNodeValues = [Int]()
23             while remainingNodesInLevel > 0 {                
24                 guard let peek = q.first else { break }
25                 q.removeFirst()                
26                 if let p = peek {                    
27                     levelNodeValues.append(p.val)
28                     if p.left != nil { q.append(p.left) }
29                     if p.right != nil { q.append(p.right) }                    
30                     remainingNodesInLevel -= 1
31                 } else {
32                     break
33                 }
34             }            
35             levelNodeValues = levelNodeValues.sorted {$0 > $1}
36             if let max = levelNodeValues.first {
37                 maxNums.append(max)
38             }            
39         }        
40         return maxNums        
41     }
42 }

128ms

 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 largestValues(_ root: TreeNode?) -> [Int] {
16         if root == nil {
17             return [Int]()
18         }
19         var queue = [(TreeNode, Int)]()
20         var result = [Int]()
21         queue.append((root!, 0))
22         while queue.count > 0 {
23             let set = queue.removeFirst()
24             if result.count <= set.1 {
25                 result.append(set.0.val)
26             } else {
27                 result[set.1] = max(result[set.1], set.0.val)
28             }
29             if set.0.left != nil {
30                 queue.append((set.0.left!, set.1 + 1))
31             }
32             if set.0.right != nil {
33                 queue.append((set.0.right!, set.1 + 1))
34             }
35         }        
36         return result
37     }
38 }