ตรวจสอบโหนดไบนารีทรีใน C ++

สมมติว่าเรามี n binary tree nodes ที่มีหมายเลขตั้งแต่ 0 ถึง n - 1 โดยที่ node I มีลูกสองคน leftChild[i] และ rightChild[i] เราต้องบอกว่าจริงก็ต่อเมื่อ โหนดที่กำหนดทั้งหมดสร้างไบนารีทรีที่ถูกต้องเพียงหนึ่งเดียว เมื่อโหนด i ไม่มีลูกด้านซ้ายแล้ว leftChild[i] จะเท่ากับ -1 เช่นเดียวกับลูกที่ถูกต้อง เราต้องจำไว้ว่าโหนดไม่มีค่าและเราใช้เฉพาะหมายเลขโหนดในปัญหานี้เท่านั้น ดังนั้นหากอินพุตเป็นแบบ −

แล้วผลลัพธ์จะเป็นจริง

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดวิธีการที่เรียกว่า dfs ซึ่งจะนำ leftChild, rightChild และเยี่ยมชม

• หากเข้าชมโหนด n ให้คืนค่าเท็จ

• แทรกโหนด n ลงในชุดที่เข้าชม

• set ret :=true

• ถ้า leftChild ของ n ไม่ใช่ -1 ดังนั้น ret :=ret AND dfs(leftChild[node], leftChild, rightChild, visit)

• ถ้า rightChild ของ n ไม่ใช่ -1 แล้ว ret :=ret AND dfs(rightChild[node], leftChild, rightChild, visit)

• รีเทิร์น

• วิธีการหลักจะเป็นเช่น -

• ret :=dfs(0, leftChild, rightChild, visit)

• set allVisited :=false

• สำหรับฉันอยู่ในช่วง 0 ถึง n – 1

  • ถ้าฉันไม่มาเยี่ยมก็คืนค่าเท็จ

• รีเทิร์น

ตัวอย่าง (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