968. Binary Tree Cameras

LeetCode hard original: C# #array #csharp #hard #leetcode #math #recursion #tree #two-pointers

Le texte du problème est traduit du russe pour la langue sélectionnée. Le code reste inchangé.

LeetCode Static

Вам дан корень бинарного дерева. Мы устанавливаем камеры на узлы дерева, где каждая камера на узле может наблюдать за своим родителем, собой и своими непосредственными детьми.

return минимальное количество камер, необходимых для наблюдения за всеми узлами дерева.

Exemple:

Input: root = [0,0,null,0,null,0,null,null,0]

Output: 2

Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.

C# solution

correspondant/original

public class Solution {
    public int MinCameraCover(TreeNode root) {
        var ans = Solve(root);
        return Math.Min(ans[1], ans[2]);
    }
    private int[] Solve(TreeNode node) {
        if (node == null) {
            return new int[] { 0, 0, 99999 };
        }
        var L = Solve(node.left);
        var R = Solve(node.right);
        int mL12 = Math.Min(L[1], L[2]);
        int mR12 = Math.Min(R[1], R[2]);
        int d0 = L[1] + R[1];
        int d1 = Math.Min(L[2] + mR12, R[2] + mL12);
        int d2 = 1 + Math.Min(L[0], mL12) + Math.Min(R[0], mR12);
        return new int[] { d0, d1, d2 };
    }
}

C++ solution

brouillon automatique, à relire avant soumission

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

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MinCameraCover(TreeNode root) {
        var ans = Solve(root);
        return min(ans[1], ans[2]);
    }
    private vector<int>& Solve(TreeNode node) {
        if (node == null) {
            return new int[] { 0, 0, 99999 };
        }
        var L = Solve(node.left);
        var R = Solve(node.right);
        int mL12 = min(L[1], L[2]);
        int mR12 = min(R[1], R[2]);
        int d0 = L[1] + R[1];
        int d1 = min(L[2] + mR12, R[2] + mL12);
        int d2 = 1 + min(L[0], mL12) + min(R[0], mR12);
        return new int[] { d0, d1, d2 };
    }
}

Java solution

correspondant/original

class Solution {
    public int minCameraCover(TreeNode root) {
        int[] ans = solve(root);
        return Math.min(ans[1], ans[2]);
    }

    public int[] solve(TreeNode node) {
        if (node == null)
            return new int[]{0, 0, 99999};

        int[] L = solve(node.left);
        int[] R = solve(node.right);
        int mL12 = Math.min(L[1], L[2]);
        int mR12 = Math.min(R[1], R[2]);

        int d0 = L[1] + R[1];
        int d1 = Math.min(L[2] + mR12, R[2] + mL12);
        int d2 = 1 + Math.min(L[0], mL12) + Math.min(R[0], mR12);
        return new int[]{d0, d1, d2};
    }
}

JavaScript solution

correspondant/original

var minCameraCover = function(root) {
    const solve = (node) => {
        if (!node) return [0, 0, 99999]

        const L = solve(node.left)
        const R = solve(node.right)
        const mL12 = Math.min(L[1], L[2])
        const mR12 = Math.min(R[1], R[2])

        const d0 = L[1] + R[1]
        const d1 = Math.min(L[2] + mR12, R[2] + mL12)
        const d2 = 1 + Math.min(L[0], mL12) + Math.min(R[0], mR12)
        return [d0, d1, d2]
    }

    const ans = solve(root)
    return Math.min(ans[1], ans[2])
}

Python solution

correspondant/original

class Solution:
    def minCameraCover(self, root: TreeNode) -> int:
        def solve(node):
            if not node:
                return 0, 0, float('inf')

            L = solve(node.left)
            R = solve(node.right)
            mL12 = min(L[1], L[2])
            mR12 = min(R[1], R[2])

            d0 = L[1] + R[1]
            d1 = min(L[2] + mR12, R[2] + mL12)
            d2 = 1 + min(L[0], mL12) + min(R[0], mR12)
            return d0, d1, d2

        return min(solve(root)[1:])

Vacancies for this task

offres actives with overlapping task tags are affichés.

Toutes les offres

Il n'y a pas encore d'offres actives.