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

Danh sách được liên kết trong cây nhị phân trong C ++

Giả sử chúng ta có gốc cây nhị phân và danh sách liên kết với phần đầu là nút đầu tiên. Chúng ta phải trả về True nếu tất cả các phần tử trong danh sách liên kết bắt đầu từ phần đầu tương ứng với một số đường dẫn xuống được kết nối trong cây nhị phân nếu không thì False. Vì vậy, nếu cây như -

Danh sách được liên kết trong cây nhị phân trong C ++

Và danh sách được liên kết là [1,4,2,6], thì kết quả đầ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 dp bản đồ

  • Xác định một phương thức có tên là giải quyết (), phương thức này sẽ lấy head, root và flag

  • nếu phần đầu là null, thì trả về true, hoặc nếu phần gốc là null, trả về false

  • nếu dp có phần đầu và dp [head] có gốc và dp [head, root] có cờ, thì trả về dp [head, root, flag]

  • nếu giá trị của head =giá trị của gốc thì

    • ret:=giải quyết (bên cạnh phần đầu, bên trái phần gốc, sai) hoặc giải quyết (bên cạnh phần đầu, bên phải phần gốc, sai)

    • nếu ret được đặt, thì dp [head, root, flag]:=true và trả về dp [head, root, flag]

    • dp [head, root, flag] =giải quyết (phần đầu, bên trái của thư mục gốc, cờ) HOẶC giải quyết (phần đầu, bên phải của thư mục gốc, cờ)

    • trả về dp [head, root, flag]

  • ngược lại, khi cờ không được đặt, thì trả về dp [head, root, flag]:=false

  • nếu không trả về dp [head, root, flag]:=giải quyết (đầu, bên trái của thư mục gốc, cờ) hoặc giải quyết (đầu, bên phải của thư mục gốc, cờ)

  • Từ phương thức chính, hãy gọi giải quyết (head, root, true)

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 ListNode{
   public:
      int val;
      ListNode *next;
      ListNode(int data){
         val = data;
         next = NULL;
      }
};
ListNode *make_list(vector<int> v){
   ListNode *head = new ListNode(v[0]);
   for(int i = 1; i<v.size(); i++){
      ListNode *ptr = head;
      while(ptr->next != NULL){
         ptr = ptr->next;
      }
      ptr->next = new ListNode(v[i]);
   }
   return head;
}
class TreeNode{
   public:
      int val;
      TreeNode *left, *right;
      TreeNode(int data){
         val = data;
         left = right = NULL;
      }
};
void insert(TreeNode **root, int val){
   queue<TreeNode*> q;
   q.push(*root);
   while(q.size()){
      TreeNode *temp = q.front();
      q.pop();
      if(!temp->left){
         if(val != NULL)
            temp->left = new TreeNode(val);
         else
            temp->left = new TreeNode(0);
         return;
         } else {
            q.push(temp->left);
         }
         if(!temp->right){
            if(val != NULL)
               temp->right = new TreeNode(val);
            else
               temp->right = new TreeNode(0);
            return;
            } else {
               q.push(temp->right);
            }
      }
}
TreeNode *make_tree(vector<int> v){
   TreeNode *root = new TreeNode(v[0]);
   for(int i = 1; i<v.size(); i++){
      insert(&root, v[i]);
   }
   return root;
}
class Solution {
   public:
      map < ListNode*, map<TreeNode*, map <bool, bool>> > dp;
      bool solve(ListNode* head, TreeNode* root, bool flag = true){
         if(head == NULL) return true;
            if(!root) return false;
            if(dp.count(head) && dp[head].count(root) && dp[head]
               [root].count(flag)) return dp[head][root][flag];
            if(head->val == root->val){
               bool ret = solve(head->next, root->left, false) ||
               solve(head->next, root->right, false);
               if(ret) return dp[head][root][flag] = true;
                  return dp[head][root][flag] = solve(head, root->left,
                  flag) || solve(head, root->right, flag);
               }else if(!flag) return dp[head][root][flag] = false;
               else
                  return dp[head][root][flag]= solve(head, root->left,
                  flag) || solve(head, root->right, flag);
         }
         bool isSubPath(ListNode* head, TreeNode* root) {
            return solve(head, root);
      }
};
main(){
   vector<int> v = {1,4,2,6};
   vector<int> v1 = {1,4,4,NULL,2,2,NULL,1,NULL,6,8,NULL,NULL,NULL,NULL,1,3};
   ListNode *head = make_list(v);
   TreeNode *root = make_tree(v1);
   Solution ob;
   cout << (ob.isSubPath(head, root));
}

Đầu vào 

[1,4,2,6]
[1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]

Đầu ra 

1