Computer >> Máy Tính >  >> Lập trình >> C ++

Kiểm tra xem một chuỗi có phải là một chuỗi hợp lệ từ đường dẫn gốc đến lá trong cây nhị phân trong C ++ hay không

Giả sử chúng ta có một cây nhị phân trong đó mỗi đường đi từ gốc đến bất kỳ lá nào đều tạo thành một chuỗi hợp lệ, chúng ta phải kiểm tra xem một chuỗi đã cho có phải là một chuỗi hợp lệ trong cây nhị phân đó hay không.

Chúng ta sẽ nhận được chuỗi đã cho từ việc ghép một mảng các số nguyên arr và việc ghép tất cả các giá trị của các nút dọc theo một đường dẫn sẽ tạo thành một chuỗi

Giả sử chúng ta có một cây nhị phân như.

Kiểm tra xem một chuỗi có phải là một chuỗi hợp lệ từ đường dẫn gốc đến lá trong cây nhị phân trong C ++ hay không

Vì vậy, nếu arr =[0,1,0,1], thì đầu ra sẽ là True, vì đường dẫn 0 -> 1 -> 0 -> 1 là một chuỗi hợp lệ (màu xanh lục). Các chuỗi hợp lệ khác sẽ là:0 -> 1 -> 1 -> 0, 0 -> 0 -> 0

Để 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 hàm giải quyết (), điều này sẽ lấy nút, một mảng v, idx khởi tạo nó bằng 0,

  • nếu nút là null, thì -

    • trả về false

  • nếu idx> =kích thước của v, thì -

    • trả về false

  • nếu val của nút không bằng v [idx] thì -

    • trả về false

  • nếu nút không có con, thì -

    • trả về true khi idx ==kích thước của v

  • trả về giải quyết (bên trái của nút, v, idx + 1)

  • từ phương thức chính, hãy làm như sau -

  • trả về giải quyết (root, arr)

Ví dụ

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 TreeNode{
public:
   int val;
   TreeNode *left, *right;
   TreeNode(int data){
      val = data;
      left = NULL;
      right = NULL;
   }
};
class Solution {
public:
   bool solve(TreeNode* node, vector <int>& v, int idx = 0){
      if(!node) return false;
      if(idx >= v.size()) return false;
      if(node->val != v[idx]) return false;
      if(!node->left && !node->right){
         return idx == v.size() - 1;
      }
      return solve(node->left, v, idx + 1) || solve(node->right, v, idx + 1);
   }
   bool isValidSequence(TreeNode* root, vector<int>& arr) {
      return solve(root, arr);
   }
};
main(){
   TreeNode *root = new TreeNode(0);
   root->left = new TreeNode(1); root->right = new TreeNode(0);
   root->left->left = new TreeNode(0); root->left->right = new
   TreeNode(1);
   root->right->left = new TreeNode(0);
   root->left->left->right = new TreeNode(1);
   root->left->right->left = new TreeNode(0); root->left->right->right = new TreeNode(0);
   Solution ob;
   vector<int> v = {0,1,0,1};
   cout << (ob.isValidSequence(root, v));
}

Đầu vào 

TreeNode *root = new TreeNode(0);
root->left = new TreeNode(1); root->right = new TreeNode(0);
root->left->left = new TreeNode(0); root->left->right = new
TreeNode(1);
root->right->left = new TreeNode(0);
root->left->left->right = new TreeNode(1);
root->left->right->left = new TreeNode(0); root->left->right->right = new TreeNode(0);

Đầu ra 

1