[Swift]LeetCode102. 二叉树的层次遍历 | Binary Tree Level Order Traversal
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
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],
3
/ \
9 20
/ \
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
返回其层次遍历结果：
[ [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 }