[Leet Code] Binary Tree Cameras

こんにちは!
今日、5月の3週目の2番目のアルゴリズムBinary Tree Camerasプールについて書きます.

質問する

サマリ
特定のツリー内のすべてのノードを監視するためにカメラをインストールする必要があります.
カメラをインストールすると、親ノードと下の子ノードを直接監視できます.
この場合、問題は、必要なカメラの最低数を返すことです.

初めて試した方法

問題は、TreeNodeというバイナリツリー構造体が固定されていることです.
カメラ数を効率的に計算するには、leafノードから検索を開始すべきだと思います.
最初は整数値で検証したが,論理的毒性が悪く理解し難い.

2回目の試みの方法

したがって、enumを使用して、現在のノードが監視されているノードなのか、監視が必要なノードなのかを判断するために、サブノードのtypeをチェックします.
必要なカメラの数を条件通りに返した結果、受け入れられました.

コードの説明

int answer = 0;

Solutionクラスのグローバル変数を使用してanswerを初期化します.

enum Monitoring {
    NONE, MONITORING, REQUIRED
}

enumは、上記のように設定されています.dfsメソッドを使用しているため、サブノードがない場合もチェックを行う必要があります.
したがって、ノードがない場合はNONE、監視中の場合はMONITORING、監視が必要な場合はREQUIREDとする.

private Monitoring dfs(TreeNode node) {
    if (node == null) return Monitoring.NONE;
    Monitoring leftType = dfs(node.left);
    Monitoring rightType = dfs(node.right);
    
    // ...
}

leafノードに入るとノードが存在しない場合は、NONEを返します.
ノードが存在する場合、左側のサブノードのタイプはleftTypeに設定され、右側のサブノードのタイプはrightTypeに設定され、dfsが呼び出される.

private Monitoring dfs(TreeNode node) {
	// ...

    if (leftType == Monitoring.NONE && rightType == Monitoring.NONE) return Monitoring.REQUIRED;
    else if ((leftType == Monitoring.MONITORING && rightType != Monitoring.REQUIRED) || (rightType == Monitoring.MONITORING && leftType != Monitoring.REQUIRED))
        return Monitoring.NONE;
    answer++;
    return Monitoring.MONITORING;
}

条件
1.サブノードがない場合は、leafノードであり、REQUIREDタイプを返します.
2.いずれかのサブノードが監視されている場合、他のノードが監視されている場合、またはノードが存在しない場合、NONEタイプが返されます.これは、次のノードが監視されていることを意味します.
3.上記でない場合は、カメラを追加し、MONITORINGタイプ(監視中)に戻ります.

public int minCameraCover(TreeNode root) {
    return (dfs(root) == Monitoring.REQUIRED) ? answer + 1: answer;
}

次に、return文に割り当てられたminCameraCover関数からdfs関数を呼び出します.dfs(root) == Monitoring.REQUIREDは、rootノードからleafノードまでがチェックされていることを示し、rootノードを監視する必要があることを意味する.
したがって、1は、これまでに検査されたanswerに加えられる.

完全なコード

class Solution {
    int answer = 0;

    public int minCameraCover(TreeNode root) {
        return (dfs(root) == Monitoring.REQUIRED) ? answer + 1: answer;
    }

    private Monitoring dfs(TreeNode node) {
        if (node == null) return Monitoring.NONE;
        Monitoring leftType = dfs(node.left);
        Monitoring rightType = dfs(node.right);

        if (leftType == Monitoring.NONE && rightType == Monitoring.NONE) return Monitoring.REQUIRED;
        else if ((leftType == Monitoring.MONITORING && rightType != Monitoring.REQUIRED) || (rightType == Monitoring.MONITORING && leftType != Monitoring.REQUIRED))
            return Monitoring.NONE;
        answer++;
        return Monitoring.MONITORING;
    }
}

enum Monitoring {
    NONE, MONITORING, REQUIRED
}

の最後の部分

比較的速い時間で私を喜ばせる問題を解決しました.
また、Javaでは、あまり多くのタイプのenumは使われていないので、これからは整数で条件を賭けるよりも、enumをよく使うべきだと思います.
今回の位置付けを読んでいただき、ありがとうございました:)