-
Notifications
You must be signed in to change notification settings - Fork 889
/
BinaryTreePaths.swift
45 lines (39 loc) · 1.17 KB
/
BinaryTreePaths.swift
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
* Question Link: https://leetcode.com/problems/binary-tree-paths/
* Primary idea: Classic DFS problem, add the path to paths when the node is leaf
* Time Complexity: O(n), Space Complexity: O(n)
*
* Definition for a binary tree node.
* public class TreeNode {
* public var val: Int
* public var left: TreeNode?
* public var right: TreeNode?
* public init(_ val: Int) {
* self.val = val
* self.left = nil
* self.right = nil
* }
* }
*/
class BinaryTreePaths {
func binaryTreePaths(_ root: TreeNode?) -> [String] {
var paths = [String]()
guard let root = root else {
return paths
}
dfs(root, &paths, "\(root.val)")
return paths
}
private func dfs(_ root: TreeNode, _ paths: inout [String], _ path: String) {
if root.left == nil && root.right == nil {
paths.append(path)
return
}
if let left = root.left {
dfs(left, &paths, path + "->\(left.val)")
}
if let right = root.right {
dfs(right, &paths, path + "->\(right.val)")
}
}
}