Xác thực các mã cây nhị phân trong C ++

Giả sử chúng ta có n nút cây nhị phân được đánh số từ 0 đến n - 1 trong đó nút I có hai nút con leftChild [i] và rightChild [i], chúng ta phải nói đúng nếu và chỉ khi tất cả các nút đã cho tạo thành chính xác một cây nhị phân hợp lệ. Khi nút i không có nút con bên trái thì leftChild [i] sẽ bằng -1, tương tự đối với nút con bên phải. Chúng ta phải nhớ rằng các nút không có giá trị và chúng ta chỉ sử dụng số nút trong bài toán này. Vì vậy, nếu đầu vào giống như -

Khi đó đầu ra sẽ là true.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một phương thức được gọi là dfs, phương thức này sẽ đưa leftChild, rightChild và được truy cập

• nếu nút n được truy cập, thì trả về false

• chèn nút n vào tập đã truy cập

• đặt ret:=true

• nếu leftChild của n không phải là -1, thì ret:=ret AND dfs (leftChild [node], leftChild, rightChild, đã thăm)

• nếu rightChild của n không phải là -1, thì ret:=ret AND dfs (rightChild [node], leftChild, rightChild, đã thăm)

• trả lại ret

• Phương thức chính sẽ giống như -

• ret:=dfs (0, leftChild, rightChild, đã thăm)

• set allVisited:=false

• cho tôi trong phạm vi từ 0 đến n - 1

  • nếu tôi không được đến thăm, thì trả về false

• trả lại ret

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

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

Đầu ra

1