Задача: 814. Binary Tree Pruning
Сложность: 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 {
    function pruneTree($root) {
        return $this->containsOne($root) ? $root : null;
    }

    private function containsOne($node) {
        if ($node === null) return false;

        $leftContainsOne = $this->containsOne($node->left);
        $rightContainsOne = $this->containsOne($node->right);

        if (!$leftContainsOne) $node->left = null;
        if (!$rightContainsOne) $node->right = null;

        return $node->val === 1 || $leftContainsOne || $rightContainsOne;
    }
}

Ставь 👍 и забирай 📚 Базу знаний