968. Binary Tree Cameras

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

Văn bản bài toán được dịch từ tiếng Nga theo ngôn ngữ giao diện. Mã không thay đổi.

LeetCode Static

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

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

Ví dụ:

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# lời giải

đã khớp/gốc

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++ lời giải

bản nháp tự động, xem lại trước khi gửi

#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 lời giải

đã khớp/gốc

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 lời giải

đã khớp/gốc

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 lời giải

đã khớp/gốc

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

việc làm đang hoạt động with overlapping task tags are đã hiển thị.

Tất cả việc làm

Chưa có việc làm đang hoạt động.