รายการที่เชื่อมโยงในไบนารีทรีใน C ++

สมมติว่าเรามีรูทแบบไบนารีและรายการที่เชื่อมโยงโดยมีส่วนหัวเป็นโหนดแรก เราต้องคืนค่า True หากองค์ประกอบทั้งหมดในรายการที่เชื่อมโยงโดยเริ่มจากส่วนหัวสอดคล้องกับเส้นทางลงที่เชื่อมต่อในไบนารีทรีมิฉะนั้นจะเป็นเท็จ ดังนั้นถ้าต้นไม้เป็นเหมือน −

และรายการที่เชื่อมโยงคือ [1,4,2,6] ดังนั้นผลลัพธ์จะเป็นจริง

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

• กำหนดแผนที่ dp

• กำหนดวิธีการที่เรียกว่า Solve() ซึ่งจะใช้ head, root และ flag

• ถ้า head เป็น null ก็คืนค่า true หรือ ถ้า root เป็น null ให้คืนค่า false

• ถ้า dp มี head และ dp[head] มีรูท และ dp[head, root] มีแฟล็ก ให้ส่งคืน dp[head, root, flag]

• ถ้าค่าของ head =ค่าของรูทแล้ว

  • ret :=แก้(ข้างหัว ซ้ายของรูท เป็นเท็จ) หรือแก้ (ข้างหัว ขวาของรูท เป็นเท็จ)

  • หากตั้งค่า ret แล้ว dp[head, root, flag] :=true และคืนค่า dp[head, root, flag]

  • dp[head, root, flag] =แก้ (หัว, ซ้ายของรูท, แฟล็ก) หรือ แก้ (หัว, ทางขวาของรูท, แฟล็ก)

  • ส่งคืน dp[head, root, flag]

• มิฉะนั้นเมื่อไม่ได้ตั้งค่าแฟล็ก ให้ส่งคืน dp[head, root, flag] :=false

• มิฉะนั้น ให้คืนค่า dp[head, root, flag] :=Solve(head, left of root, flag) หรือแก้ปัญหา (head, right of root, flag)

• จากการเรียกเมธอดหลัก (head, root, true)

ตัวอย่าง (C++)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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

อินพุต

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

ผลลัพธ์

1