Swift solution - DFS, BFS


  • 0
    class Solution {
        func zigzagLevelOrder(_ root: TreeNode?) -> [[Int]] {
            guard let root = root else {
                return []
            }
            
            var result = [[Int]]()
            
            DFS(root, &result, 0)
            
            return result
        }
        
        func DFS(_ node: TreeNode?, _ result: inout [[Int]], _ level: Int) {
            guard let node = node else {
                return
            }
            
            if result.count <= level {
                result.append([Int]())
            }
            
            var levelNodes = result[level]
            if level % 2 == 0 {
                levelNodes.append(node.val)
            } else {
                levelNodes.insert(node.val, at: 0)
            }
            result[level] = levelNodes
            
            DFS(node.left, &result, level + 1)
            DFS(node.right, &result, level + 1)
        }
        
        func zigzagLevelOrder_BFS(_ root: TreeNode?) -> [[Int]] {
            guard let root = root else {
                return []
            }
            
            var result = [[Int]]()
            var order = true
            var queue = [TreeNode]()
            
            queue.append(root)
            while !queue.isEmpty {
                var levelNodes = [Int]()
                let count = queue.count
                for _ in 0..<count {
                    let node = queue.removeFirst()
                    if order {
                        levelNodes.append(node.val)
                    } else {
                        levelNodes.insert(node.val, at: 0)
                    }
                    if let leftNode = node.left {
                        queue.append(leftNode)
                    }
                    if let rightNode = node.right {
                        queue.append(rightNode)
                    }
                }
                result.append(levelNodes)
                order = !order
            }
            
            return result
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.