[Swift]LeetCode102.二叉树的层次遍历|BinaryTreeLevelOrderTraversal

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

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

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

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

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

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

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

给定一个二叉树，返回其按层次遍历的节点值。（即逐层地，从左到右访问所有节点）。

例如:
给定二叉树: [3,9,20,null,null,15,7],

返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

12ms

 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 levelOrder(_ root: TreeNode?) -> [[Int]] {
16         var resArray = [[Int]]()
17         if root == nil {
18             return resArray
19         }
20         
21         if root?.left == nil && root?.right == nil {
22             let array = [Int](repeating:root!.val, count:1)
23             resArray.append(array)
24             return resArray
25         }
26         
27         var currentLevelNodes = [TreeNode]()
28         currentLevelNodes.append(root!)
29 
30         helper(currentLevelNodes,&resArray)
31 
32         return resArray
33     }
34 
35     fileprivate func helper(_ nodesArray:[TreeNode], _ array: inout [[Int]]) -> Void {
36         
37         var valArray = [Int]()
38         var nextLevelArray = [TreeNode]()
39         
40         for i in 0 ..< nodesArray.count {
41             let node = nodesArray[i]
42             valArray.append(node.val)
43             
44             if node.left != nil {
45                 nextLevelArray.append(node.left!)
46             }
47 
48             if node.right != nil {
49                 nextLevelArray.append(node.right!)
50             }
51         }
52         
53         array.append(valArray)
54 
55         if nextLevelArray.count > 0 {
56             helper(nextLevelArray,&array)
57         }
58     }
59 }

16ms

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

16ms

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

20ms

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

24ms

 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 levelOrder(_ root: TreeNode?) -> [[Int]] {
16         var res = [[Int]]()
17         guard let _root = root else {
18             return res
19         }
20         var nodeq = [_root]
21         while(nodeq.count > 0){
22             res.append(nodeq.map{ $0.val })
23             
24             nodeq = nodeq.flatMap{ [$0.left, $0.right].compactMap{ $0 } }
25         }
26         return res
27     }
28 }

28ms

 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     public class QueueTreeNode {
16         public var treeNode: TreeNode?
17         public var level: Int?
18         public init(_ node: TreeNode,_ level: Int) {
19             self.treeNode = node
20             self.level = level
21         }
22     }
23 
24 
25 var queue: [QueueTreeNode] = []
26     
27     func inQueue(_ item: QueueTreeNode?){
28         if let item = item {
29             queue.append(item)
30         }
31     }
32     
33     func deQueue() -> QueueTreeNode? {
34         if queue.isEmpty {
35             return nil
36         } else {
37             let outItem = queue[0]
38             queue.remove(at:0)
39             return outItem
40         }
41     }
42     
43     func levelOrder(_ root: TreeNode?) -> [[Int]] {
44         var result: [[Int]] = [[]]
45     
46         guard let root = root else { return [] }
47     
48         inQueue(QueueTreeNode(root,0))
49     
50         while !queue.isEmpty {
51             guard let newItem = deQueue() else { break }
52         
53             if result[newItem.level!].isEmpty {
54                 result.append([])
55             }
56         
57             result[newItem.level!].append(newItem.treeNode!.val)
58         
59             if let leftNode = newItem.treeNode!.left {
60                 inQueue(QueueTreeNode(leftNode, newItem.level! + 1))
61             }
62         
63             if let rightNode = newItem.treeNode!.right {
64                 inQueue(QueueTreeNode(rightNode, newItem.level! + 1))
65             }
66         }
67         result.removeLast()
68         return result
69     }
70 }

28ms

 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 levelOrder(_ root: TreeNode?) -> [[Int]] {
16         var res: [[Int]] = []
17         
18         var stack: [[TreeNode]] = []
19         if let root = root {
20             stack.append([root])
21         }
22         
23         while !stack.isEmpty {
24             let nodes = stack.popLast()!
25             var vals: [Int] = []
26             var nextNodes: [TreeNode] = []
27             for node in nodes {
28                 vals.append(node.val)
29                 if let left = node.left {
30                     nextNodes.append(left)
31                 }
32                 if let right = node.right {
33                     nextNodes.append(right)
34                 }
35             }
36             res.append(vals)
37             if !nextNodes.isEmpty {
38                 stack.append(nextNodes)
39             }
40         }
41         
42         return res
43     }
44 }

148ms

 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 levelOrder(_ root: TreeNode?) -> [[Int]] {
16         var order: [[Int]] = []
17         var nodes: [TreeNode] = [root].flatMap { $0 }
18 
19         while !nodes.isEmpty {
20             order.append(nodes.flatMap { $0.val } )
21 
22             nodes = nodes.flatMap({ (node) -> [TreeNode] in
23                 return [node.left, node.right].flatMap { $0 }
24             })
25         }
26 
27         return order
28     }
29 }