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

发布时间：2020-12-14 05:04:04 所属栏目：百科来源：网络整理

导读：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,9] 48ms 1 /* * 2 * Definition for a binar

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,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,&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,&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 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!