968. Binary Tree Cameras

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

El texto de la tarea se traduce del ruso para el idioma seleccionado. El código no cambia.

LeetCode Static

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

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

Ejemplo:

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# solución

coincidente/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++ solución

borrador automático, revisar antes de enviar

#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 solución

coincidente/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 solución

coincidente/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 solución

coincidente/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:])

Vacantes para esta tarea

Se muestran vacantes activas con etiquetas coincidentes.

Todas las vacantes

Todavía no hay vacantes activas.