Сложность: easy
Дано корневое дерево, верните все пути от корня до листа в любом порядке.
Лист — это узел без детей.
Пример:
Input: root = [1,2,3,null,5]
Output: ["1->2->5","1->3"]
👨💻 Алгоритм:
1⃣Если текущий узел не является null, добавьте его значение к текущему пути.
Если текущий узел является листом (не имеет дочерних узлов), добавьте текущий путь в список путей.
Если текущий узел не является листом, добавьте "->" к текущему пути и рекурсивно вызовите функцию для левого и правого дочерних узлов.
2⃣Начните с корневого узла, пустого пути и пустого списка путей.
3⃣Верните список всех путей от корня до листа.
😎 Решение:
class Solution {
func construct_paths(_ root: TreeNode?, _ path: String, _ paths: inout [String]) {
if let root = root {
var path = path + "\(root.val)"
if root.left == nil && root.right == nil {
paths.append(path)
} else {
path += "->"
construct_paths(root.left, path, &paths)
construct_paths(root.right, path, &paths)
}
}
}
func binaryTreePaths(_ root: TreeNode?) -> [String] {
var paths = [String]()
construct_paths(root, "", &paths)
return paths
}
}Ставь 👍 и забирай 📚 Базу знаний