[Swift]LeetCode103.二叉树的锯齿形层次遍历|BinaryTreeZigzagLevelOrderTraversal ...

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 zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

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

return its zigzag level order traversal as:

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

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

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

返回锯齿形层次遍历如下：

[
  [3],
  [20,9],
  [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 zigzagLevelOrder(_ root: TreeNode?) -> [[Int]] {
16         guard let root = root else {
17             return []
18         }
19         
20         var result = [[Int]]()
21         var order = true
22         var queue = [TreeNode]()
23         
24         queue.append(root)
25         while !queue.isEmpty {
26             var levelNodes = [Int]()
27             let count = queue.count
28             for _ in 0..<count {
29                 let node = queue.removeFirst()
30                 if order {
31                     levelNodes.append(node.val)
32                 } else {
33                     levelNodes.insert(node.val, at: 0)
34                 }
35                 if let leftNode = node.left {
36                     queue.append(leftNode)
37                 }
38                 if let rightNode = node.right {
39                     queue.append(rightNode)
40                 }
41             }
42             result.append(levelNodes)
43             order = !order
44         }
45         
46         return result
47     }
48 }

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

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 zigzagLevelOrder(_ root: TreeNode?) -> [[Int]] {
16     var treeValArray = [[Int]]()
17     guard let root = root else {
18         return treeValArray
19     }
20     var nodeArray = [TreeNode]()
21     nodeArray.append(root)
22     var isleft = false
23     while !nodeArray.isEmpty {
24         let queueArray = nodeArray
25         nodeArray.removeAll()
26         var valArray = [Int]()
27         for node in queueArray{
28             valArray.append(node.val)
29         }
30         for node in queueArray.reversed(){
31             if isleft{
32                 if node.left != nil{
33                     nodeArray.append(node.left!)
34                 }
35                 if node.right != nil{
36                     nodeArray.append(node.right!)
37                 }
38             }else{
39                 if node.right != nil{
40                     nodeArray.append(node.right!)
41                 }
42                 if node.left != nil{
43                     nodeArray.append(node.left!)
44                 }
45             }
46         }
47         isleft = !isleft
48         treeValArray.append(valArray)
49     }
50     return treeValArray
51     }
52 }

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

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 zigzagLevelOrder(_ root: TreeNode?) -> [[Int]] {
16         var result = [[Int]]()
17         guard root != nil else {
18             return result
19         }
20         var queue = [TreeNode]()
21         queue.append(root!)
22         var shouldEnqueueRightFirst = false
23         while !queue.isEmpty {
24             var newQueue = [TreeNode]()
25             var level = [Int]()
26             for node in queue.reversed() {
27                 level.append(node.val)
28                 if shouldEnqueueRightFirst {
29                     if node.right != nil {
30                         newQueue.append(node.right!)
31                     }
32                     if node.left != nil {
33                         newQueue.append(node.left!)
34                     }
35                 } else {
36                     if node.left != nil {
37                         newQueue.append(node.left!)
38                     }
39                     if node.right != nil {
40                         newQueue.append(node.right!)
41                     }   
42                 }
43             }
44             queue = newQueue
45             result.append(level)
46             shouldEnqueueRightFirst = !shouldEnqueueRightFirst
47         }
48         return result
49     }
50 }

36ms

 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 ret = [[Int]]()
16     func zigzagLevelOrder(_ root: TreeNode?) -> [[Int]] {
17         guard let root = root else { return ret }
18         dfs(root, 0)
19         return ret
20     }
21     
22     private func dfs(_ root: TreeNode?, _ level: Int) {
23         guard let root = root else { return }
24         
25         if ret.count > level {
26             print("array at level: \(level) already exists: \(ret[level])")
27             if level % 2 == 0 {
28                 ret[level].append(root.val)
29             } else {
30                 ret[level].insert(root.val, at: 0)
31             }
32         } else {
33             print("creating new array at level: \(level)")
34             ret.append([Int]())
35             ret[level].append(root.val)
36         }
37         dfs(root.left, level+1)
38         dfs(root.right, level+1)
39     }
40 }

52ms

 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 zigzagLevelOrder(_ root: TreeNode?) -> [[Int]] {
16         var res: [[Int]] = []
17         guard let root = root else {
18             return []
19         }
20         zigZagLevel(nodes: [root], ltr: true, val: &res)
21         return res
22     }
23     
24     func zigZagLevel(nodes: [TreeNode], ltr: Bool, val: inout [[Int]]){
25         
26         //var looping = ltr ? stride(from: 0, to: nodes.count, by: 1) : stride(from: nodes.count - 1, to: -1, by: -1)
27         var looping = stride(from: 0, to: nodes.count, by: 1)
28         
29         var nextLevel: [TreeNode] = []
30         var currentVal: [Int] = []
31         for nodeIndex in looping{
32             print(1)
33             currentVal.append(nodes[nodeIndex].val)
34             if let left = nodes[nodeIndex].left {
35                 if let right = nodes[nodeIndex].right {
36                 
37                     let next = [left,right]
38                     print("next", next)
39                     nextLevel += next
40                     print("Next level after append", nextLevel)
41                 }  else {
42                     print("only left")
43                     nextLevel += [left]
44                 }
45             } else if let right = nodes[nodeIndex].right {
46                 print("only right")
47                 nextLevel += [right]
48             }
49         }
50         print(currentVal)
51         if !ltr { currentVal.reverse()}
52         if currentVal.count > 0 { val.append(currentVal) }
53         print("val after append", val)
54         if nextLevel.count > 0 {
55             zigZagLevel(nodes: nextLevel, ltr: !ltr, val: &val)
56         }
57     }
58 }