C++에서 이진 트리 노드 유효성 검사

0에서 n - 1까지 번호가 매겨진 n개의 이진 트리 노드가 있다고 가정하고 노드 I에 두 개의 자식이 leftChild[i]와 rightChild[i]가 있다고 가정하면 다음 경우에만 true라고 말해야 합니다. 주어진 모든 노드는 정확히 하나의 유효한 이진 트리를 형성합니다. 노드 i에 왼쪽 자식이 없으면 leftChild[i]는 오른쪽 자식과 마찬가지로 -1이 됩니다. 노드에는 값이 없으며 이 문제에서는 노드 번호만 사용한다는 점을 명심해야 합니다. 따라서 입력이 다음과 같으면 -

그러면 출력이 true가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• dfs라는 메서드를 정의하면 leftChild, rightChild 및 Visited가 사용됩니다.

• 노드 n을 방문하면 false를 반환합니다.

• 노드 n을 방문 세트에 삽입

• 설정 ret :=true

• n의 leftChild가 -1이 아니면 ret :=ret AND dfs(leftChild[node], leftChild, rightChild, 방문)

• n의 rightChild가 -1이 아니면 ret :=ret AND dfs(rightChild[node], leftChild, rightChild, 방문)

• 리턴 렛

• 주요 방법은 다음과 같습니다 -

• ret :=dfs(0, leftChild, rightChild, 방문)

• set allVisited :=false

• 0 ~ n – 1 범위의 I

  • 내가 방문하지 않으면 false를 반환합니다.

• 리턴 렛

예시(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