814. Binary Tree Pruning

LeetCode оригинал: C# #csharp #leetcode #tree #two-pointers

LeetCode Static

: 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.

C# решение

сопоставлено/оригинал

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Solution {
    public TreeNode PruneTree(TreeNode root) {
        return ContainsOne(root) ? root : null;
    }
    private bool ContainsOne(TreeNode node) {
        if (node == null) return false;
        bool leftContainsOne = ContainsOne(node.left);
        bool rightContainsOne = ContainsOne(node.right);
        if (!leftContainsOne) node.left = null;
        if (!rightContainsOne) node.right = null;
        return node.val == 1 || leftContainsOne || rightContainsOne;
    }
}

C++ решение

auto-draft, проверить перед отправкой

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
class Solution {
public:
    public TreeNode PruneTree(TreeNode root) {
        return ContainsOne(root) ? root : null;
    }
    private bool ContainsOne(TreeNode node) {
        if (node == null) return false;
        bool leftContainsOne = ContainsOne(node.left);
        bool rightContainsOne = ContainsOne(node.right);
        if (!leftContainsOne) node.left = null;
        if (!rightContainsOne) node.right = null;
        return node.val == 1 || leftContainsOne || rightContainsOne;
    }
}

Java решение

сопоставлено/оригинал

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;
    }

JavaScript решение

сопоставлено/оригинал

var pruneTree = function(root) {
    if (containsOne(root)) {
        return root;
    }
    return null;
};

var containsOne = function(node) {
    if (!node) return false;

    let leftContainsOne = containsOne(node.left);
    let rightContainsOne = containsOne(node.right);

    if (!leftContainsOne) node.left = null;
    if (!rightContainsOne) node.right = null;

    return node.val === 1 || le

Python решение

сопоставлено/оригинал

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

Algorithm

Используем функцию containsOne(node), которая сообщает, содержит ли поддерево в данном узле единицу, и обрезает все поддеревья, не содержащие единицу.

Например, если поддерево node.left не содержит единицу, то мы должны обрезать его через node.left = null.

Также нужно проверить родительский узел. Например, если дерево состоит из одного узла 0, то ответом будет пустое дерево.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.