C++で二分木ノードの妥当性を検証する方法

0からn-1までの番号が付けられたn個の二分木ノードがあるとします。ノードiは、leftChild[i]およびrightChild[i]で表される2つの子を持ちます。与えられたすべてのノードがちょうど1つの有効な二分木を構成する場合にのみ、trueを返す必要があります。ノードiに左の子が存在しない場合はleftChild[i]が-1となり、右の子がない場合も同様にrightChild[i]が-1になります。なお、この問題ではノードは値を持たず、ノード番号のみを使用することに注意してください。

例えば、入力が以下のような場合を考えてみましょう。

この場合、出力はtrueになります。

解決のアプローチ

この問題は、深さ優先探索(DFS)を用いて解くことができます。以下の手順に従います。

dfsメソッドの定義

• leftChild、rightChild、visitedを引数として受け取るdfsメソッドを定義します。
• ノードnがすでに訪問済み(visitedに含まれる)の場合は、falseを返します。これはサイクルの検出に相当します。
• ノードnをvisitedセットに追加します。
• retをtrueで初期化します。
• ノードnの左の子が-1でない場合、ret := ret AND dfs(leftChild[node], leftChild, rightChild, visited)とします。
• ノードnの右の子が-1でない場合、ret := ret AND dfs(rightChild[node], leftChild, rightChild, visited)とします。
• retを返します。

メイン処理の流れ

• ret := dfs(0, leftChild, rightChild, visited)を呼び出します。
• 0からn-1までのすべてのノードが訪問済みであることを確認します。未訪問のノードが1つでも存在すれば、木が連結していないためfalseを返します。
• 最後にretを返します。

実装例(C++)

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    bool dfs(int node, vector <int>& leftChild, vector <int>& rightChild, set <int>& visited){
        if(visited.count(node)) return false;
        visited.insert(node);
        bool ret = true;
        if(leftChild[node] != -1){
            ret &= dfs(leftChild[node], leftChild, rightChild, visited);
        }
        if(rightChild[node] != -1){
            ret &= dfs(rightChild[node], leftChild, rightChild, visited);
        }
        return ret;
    }
    bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
        set <int> visited;
        bool ret = dfs(0, leftChild, rightChild, visited);
        for(int i = 0; i < n; i++){
            if(!visited.count(i))return false;
        }
        return ret;
    }
};
main(){
    vector<int> v1 = {1,-1,3,-1}, v2 = {2,-1,-1,-1};
    Solution ob;
    cout << (ob.validateBinaryTreeNodes(4, v1, v2));
}

入力

4
[1,-1,3,-1]
[2,-1,-1,-1]

出力

1

このコードでは、ノード0からDFSを開始し、すべてのノードを一度だけ訪問できるかどうかを確認しています。訪問済みのノードに再び到達した場合はサイクルが存在するためfalseを返し、未訪問のノードが残っている場合は木が連結していないためfalseを返します。これにより、与えられたノード集合が有効な単一の二分木を構成しているかどうかを正確に判定できます。