Постановка задачи

Учитывая root бинарного дерева, вернуть то же дерево, где каждое поддерево (данного дерева), не содержащее 1, было удалено.

Поддерево узла node является node плюс каждый узел, который является потомком node.

Эту проблему можно найти здесь ::

Пример 1:
Описание изображения

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.
Войти в полноэкранный режим

Выйти из полноэкранного режима

Пример 2:
Описание изображения

Input: root = [1,0,1,0,0,0,1]
Output: [1,null,1,null,1]
Войти в полноэкранный режим

Выйти из полноэкранного режима

Пример 3:
Описание изображения

Input: root = [1,1,0,1,1,0,1,0]
Output: [1,1,0,1,1,null,1]
Войти в полноэкранный режим

Выйти из полноэкранного режима

Ограничения:
Количество узлов в дереве находится в диапазоне [1, 200].
Node.val равен 0 или 1.


Решение

Давайте посмотрим, как мы можем определить суждение поддерева о том, содержит ли оно 1 или нет. Это можно было сделать очень наивной техникой обхода дерева, известной DFS (поиск в глубину).

Остается один вопрос: как знание о поддереве из глубины может быть передано снизу вверх?
Давайте разберем это по крупицам. Итак, какая информация должна быть отправлена, это понимание того, 1 присутствует в поддереве или нет (т. е. должно быть возвращено логическое значение).
Теперь, основываясь на том, что нам нужно передать значение вышестоящему родителю. Для этого нам нужно проверить

  1. текущее состояние
  2. левый узел/поддерево
  3. правый узел/поддерево

то это должно сводиться к псевдокоду, как показано ниже

current_node_has_one = node.value == 1;
left_node_has_one = check_for_one(node.left)
right_node_has_one = check_for_one(node.right)
Войти в полноэкранный режим

Выйти из полноэкранного режима

сейчас если left_node_has_one или же right_node_has_one верно, то можно его сохранить. Если какое-либо одно (или оба) ложно, то соответствующее поддерево должно быть нулевым или, другими словами, должно быть удалено.

if(right_node_has_one) 
then
    node.right = null // deleted the right node
end if
Войти в полноэкранный режим

Выйти из полноэкранного режима

Теперь это нужно передать на верхний узел. Эти данные будут состоять из того, было ли текущее поддерево нулевым или нет. Это означает, current_node_has_one || left_node_has_one || right_node_has_one, и это логически должно быть в конце функции. В конце концов, условием остановки будет то, что, если узел имеет значение null, а затем возвращает false, так как это не имеет 1.

Исходя из этого, мы можем иметь следующее решение.


Временная сложность: O(n)


Сложность вспомогательного пространства: O(1)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode pruneTree(TreeNode root) {
        return fn(root)? root : null;
    }

    public boolean fn(TreeNode root) {
        if(root == null) return false;
        boolean hasOne = root.val == 1;
        boolean left = fn(root.left); if(!left) root.left = null;
        boolean right = fn(root.right); if(!right) root.right = null;
        return hasOne | left | right;
    }
}
Войти в полноэкранный режим

Выйти из полноэкранного режима