Сложность: medium
Дан корень бинарного дерева. Верните то же дерево, в котором удалены все поддеревья (данного дерева), не содержащие 1.
Поддерево узла node - это сам узел node и все узлы, являющиеся потомками node.
Пример:
Input: root = [1,null,0,0,1]
Output: [1,null,0,null,1]
Explanation:
Only the red nodes satisfy the property "every subtree not containing a 1".
The diagram on the right represents the answer.
👨💻 Алгоритм:
1⃣Используем функцию containsOne(node), которая сообщает, содержит ли поддерево в данном узле единицу, и обрезает все поддеревья, не содержащие единицу.
2⃣Например, если поддерево node.left не содержит единицу, то мы должны обрезать его через node.left = null.
3⃣Также нужно проверить родительский узел. Например, если дерево состоит из одного узла 0, то ответом будет пустое дерево.
😎 Решение:
class Solution {
func pruneTree(_ root: TreeNode?) -> TreeNode? {
return containsOne(root) ? root : nil
}
func containsOne(_ node: TreeNode?) -> Bool {
guard let node = node else { return false }
let leftContainsOne = containsOne(node.left)
let rightContainsOne = containsOne(node.right)
if !leftContainsOne { node.left = nil }
if !rightContainsOne { node.right = nil }
return node.val == 1 || leftContainsOne || rightContainsOne
}
}Ставь 👍 и забирай 📚 Базу знаний