Сложность: 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 {
public TreeNode pruneTree(TreeNode root) {
return containsOne(root) ? root : null;
}
private boolean containsOne(TreeNode node) {
if (node == null) return false;
boolean leftContainsOne = containsOne(node.left);
boolean rightContainsOne = containsOne(node.right);
if (!leftContainsOne) node.left = null;
if (!rightContainsOne) node.right = null;
return node.val == 1 || leftContainsOne || rightContainsOne;
}Ставь 👍 и забирай 📚 Базу знаний