968. Binary Tree Cameras

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

Il testo del problema è tradotto dal russo per la lingua selezionata. Il codice resta invariato.

LeetCode Static

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

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

Esempio:

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# soluzione

abbinato/originale

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++ soluzione

bozza automatica, rivedere prima dell'invio

#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 soluzione

abbinato/originale

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 soluzione

abbinato/originale

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 soluzione

abbinato/originale

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

offerte attive with overlapping task tags are mostrati.

Tutte le offerte

Non ci sono ancora offerte attive.