C++でバイナリツリーノードを検証する

0からn-1までの番号が付けられたn個の二分木ノードがあり、ノードIに2つの子leftChild[i]とrightChild[i]があるとすると、次の場合にのみtrueと言う必要があります。指定されたすべてのノードは、正確に1つの有効な二分木を形成します。ノードiに左の子がない場合、leftChild [i]は-1に等しくなります。これは、右の子の場合と同様です。ノードには値がなく、この問題ではノード番号のみを使用することに注意する必要があります。したがって、入力が-

その後、出力はtrueになります。

これを解決するには、次の手順に従います-

• dfsというメソッドを定義します。これにより、leftChild、rightChildが取得され、visitedされます

• ノードnにアクセスした場合は、falseを返します

• 訪問したセットにノードnを挿入します

• set ret：=true

• nのleftChildが-1でない場合、ret：=ret AND dfs（leftChild [node]、leftChild、rightChild、visited）

• nのrightChildが-1でない場合、ret：=ret AND dfs（rightChild [node]、leftChild、rightChild、visited）

• retを返す

• 主な方法は次のようになります-

• ret：=dfs（0、leftChild、rightChild、visited）

• allVisited：=falseを設定

• 0からn–1の範囲のIの場合

  • 私が訪問されていない場合は、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);
      bool allVisited = true;
      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