Swift solution - DFS, Stack iterative


  • 0
    class Solution {
        func binaryTreePaths(_ root: TreeNode?) -> [String] {
            guard let root = root else {
                return []
            }
            
            var paths = [String]()
            
            if root.left == nil && root.right == nil {
                paths.append(String(root.val))
                return paths
            }
            
            for path in binaryTreePaths(root.left) {
                paths.append("\(root.val)->\(path)")
            }
            for path in binaryTreePaths(root.right) {
                paths.append("\(root.val)->\(path)")
            }
            
            return paths
        }
        
        func binaryTreePaths2(_ root: TreeNode?) -> [String] {
            guard let root = root else {
                return []
            }
            
            var paths = [String]()
            
            DFS(root, "", &paths)
            
            return paths
        }
        
        func DFS(_ root: TreeNode, _ path: String, _ paths: inout [String]) {
            if root.left == nil && root.right == nil {
                paths.append(path + String(root.val))
                return
            }
            
            if let leftNode = root.left {
                DFS(leftNode, path + String(root.val) + "->", &paths)
            }
            if let rightNode = root.right {
                DFS(rightNode, path + String(root.val) + "->", &paths)
            }
        }
        
        func binaryTreePath_Stack(_ root: TreeNode?) -> [String] {
            guard let root = root else {
                return []
            }
            
            let element = (node: root, path: "")
            var stack = [element]
            var paths = [String]()
            
            while !stack.isEmpty {
                let element = stack.removeLast()
                let node = element.node
                let path = element.path
                if node.left == nil && node.right == nil {
                    paths.append(path + String(node.val))
                }
                if let rightNode = node.right {
                    let element = (node: rightNode, path: path + String(node.val) + "->")
                    stack.append(element)
                }
                if let leftNode = node.left {
                    let element = (node: leftNode, path: path + String(node.val) + "->")
                    stack.append(element)
                }
            }
            
            return paths
        }
    }
    

Log in to reply
 

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