Сложность: 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:
def pruneTree(self, root):
def containsOne(node):
if not node:
return False
leftContainsOne = containsOne(node.left)
rightContainsOne = containsOne(node.right)
if not leftContainsOne:
node.left = None
if not rightContainsOne:
node.right = None
return node.val == 1 or leftContainsOne or rightContainsOne
return root if containsOne(root) else None
Ставь 👍 и забирай 📚 Базу знаний