[Swift]LeetCode513.找树左下角的值|FindBottomLeftTreeValue

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

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

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

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

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

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

Given a binary tree, find the leftmost value in the last row of the tree.

Example 1:

Input:

    2
   / \
  1   3

Output:1

Example 2:

Input:

        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7

Output:7

Note: You may assume the tree (i.e., the given root node) is not NULL.

给定一个二叉树，在树的最后一行找到最左边的值。

示例 1:

输入:

    2
   / \
  1   3

输出:1

示例 2:

注意: 您可以假设树（即给定的根节点）不为 NULL。

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 findBottomLeftValue(_ root: TreeNode?) -> Int {
16         guard let node = root else {
17             return 0
18         }
19         
20         var currentLevel = 0
21         var currentValue = node.val
22         
23         func DFS(_ root: TreeNode?, level: Int) {
24             guard let node = root else {
25                 return
26             }
27             DFS(node.left, level: level + 1)
28             if level > currentLevel {
29                 currentLevel = level
30                 currentValue = node.val
31             }
32             DFS(node.right, level: level + 1)
33         }
34         DFS(node, level: 0)
35         return currentValue
36     }
37 }

Runtime: 64 ms

Memory Usage: 19.9 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 findBottomLeftValue(_ root: TreeNode?) -> Int {
16         var tree = [TreeNode]()
17         tree.append(root!)
18         var node = root
19         while !tree.isEmpty {
20             node = tree.removeFirst()
21             if node?.right != nil {
22                 tree.append(node!.right!)
23             }
24             if node?.left != nil {
25                 tree.append(node!.left!)
26             }
27         }
28         return node!.val    
29     }
30 }

64ms

 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 findBottomLeftValue(_ root: TreeNode?) -> Int {
16         
17         var queue = [TreeNode]()
18         
19         queue.append(root!)
20         var result = 0 
21         var level = [Int]()
22         
23         while !queue.isEmpty {
24             
25             let size = queue.count 
26             level = []
27             for i in 0 ..< size {
28                 
29                 let node = queue.removeFirst()
30                 level.append(node.val)
31                 if node.left != nil{
32                     queue.append(node.left!)
33                 }
34                 
35                 if node.right != nil{
36                     queue.append(node.right!)
37                 }
38             }
39             result = level[0]
40         }
41         
42         return result
43     }
44 }

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 findBottomLeftValue(_ root: TreeNode?) -> Int {
16         guard let root = root else { return 0}
17             
18         var value = (root.val, 0)
19         
20         if let leftNode = root.left {
21              value = helper(node: leftNode, level: 1)
22         }
23                 
24         if let rightNode = root.right {
25             let value2 = helper(node: rightNode, level: 1)
26             if value2.1 > value.1 {
27                 value = value2
28             }
29         }
30         
31         return value.0
32     }
33     
34     func helper(node: TreeNode, level: Int) -> (Int, Int) {
35         
36         var value = (node.val, level)
37                 
38         if let leftNode = node.left {
39              value = helper(node: leftNode, level: level + 1)
40         }
41         
42         if let rightNode = node.right {
43             let value2 = helper(node: rightNode, level: level + 1)
44             if value2.1 > value.1 {
45                 value = value2
46             }
47         }        
48         return value
49     }
50 }

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 class Solution {
15     func findBottomLeftValue(_ root: TreeNode?) -> Int {
16         return helper(root, 0)!.1
17     }
18     
19     func helper(_ root: TreeNode?, _ level: Int) -> (Int, Int)? {
20         guard let root = root else {
21             return nil
22         }
23 
24         let a = helper(root.left, level + 1)
25         let b = helper(root.right, level + 1)
26         if a == nil && b == nil {
27             return (level, root.val)
28         }
29         if a != nil && b != nil {
30             if a!.0 >= b!.0 {
31                 return a
32             } else {
33                 return b
34             }
35         }
36         return a ?? b
37     }
38 }

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 
15 class Queue<Type> {
16     var array: [Type] = []
17     var index = -1
18     
19     init() {
20     }
21     
22     func insert(_ T: Type) {
23         index = index + 1
24         array.append(T)
25     }
26     
27     func delete() -> Type? {
28         if (index == -1) {
29             return nil
30         }
31         
32         let ret = array[0]
33         array.remove(at: 0)
34         index = index - 1
35         
36         return ret
37     }
38     
39     func front() -> Type? {
40         if (index == -1) {
41             return nil
42         }
43         
44         let ret = array[0]
45         return ret
46     }
47     
48     func isEmpty() -> Bool {
49         return index == -1
50     }
51 }
52 
53 class Solution {
54     func findBottomLeftValue(_ root: TreeNode?) -> Int {
55         if (root == nil) {
56             return -1
57         }
58         
59         var result = -1
60         var q1 = Queue<TreeNode>()
61         var q2 = Queue<TreeNode>()
62         var temp: Queue<TreeNode> = q1
63         var level = 0
64         var stop = false
65         
66         q1.insert(root!)
67         
68         while (false == stop) {
69             
70             stop = true
71             
72             if (false == q1.isEmpty()) {
73                 result = q1.front()!.val
74             }
75             
76             while(false == q1.isEmpty()) {
77                 let node = q1.delete()
78                 if (node!.left != nil) {
79                     q2.insert(node!.left!)
80                 }
81                 if (node!.right != nil) {
82                     q2.insert(node!.right!)
83                 }
84                 stop = false
85             }
86             
87             temp = q1
88             q1 = q2
89             q2 = temp
90         }
91         
92         return result
93     }
94 }

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 class Solution {
15     var ansFi = Int.min
16     
17     var level = -1
18     
19     func findBottomLeftValue(_ root: TreeNode?) -> Int {
20         
21 
22         findBottomHelper(root: root, currentLevel: 0)
23 
24         return ansFi
25     }
26     
27     private func findBottomHelper(root: TreeNode?, currentLevel: Int) {
28         
29         guard let root = root else {
30             return
31         }
32 
33         if level+1 == currentLevel {
34             ansFi = root.val
35             level = currentLevel
36         }
37 
38         findBottomHelper(root: root.left, currentLevel: currentLevel + 1)
39 
40         findBottomHelper(root: root.right, currentLevel: currentLevel + 1)
41     }
42 }