C++のバイナリツリーのリンクリスト

二分木ルートと、最初のノードとしてヘッドを持つリンクリストがあるとします。リンクリスト内の先頭から始まるすべての要素が、バイナリツリーで接続されている下向きのパスに対応している場合はTrueを返す必要があり、そうでない場合はFalseを返す必要があります。したがって、ツリーが次のような場合-

リンクリストが[1,4,2,6]の場合、出力はtrueになります。

これを解決するには、次の手順に従います-

• マップdpを定義する

• ソルブ（）と呼ばれるメソッドを定義します。これはヘッド、ルート、フラグを取ります

• ヘッドがnullの場合はtrueを返し、ルートがnullの場合はfalseを返します

• dpにヘッドがあり、dp [head]にルートがあり、dp [head、root]にフラグがある場合は、dp [head、root、flag]

  を返します。

• ヘッドの値=ルートの値の場合、

  • ret：=solve（頭の次、ルートの左側、false）またはsolve（頭の次、ルートの右側、false）

  • retが設定されている場合、dp [head、root、flag]：=trueであり、dp [head、root、flag]

    を返します。

  • dp [head、root、flag] =resolve（head、left of root、flag）またはsolve（head、right of root、flag）

  • dp [head、root、flag]

    を返します

• それ以外の場合、フラグが設定されていない場合は、dp [head、root、flag]：=false

  を返します。

• それ以外の場合は、dp [head、root、flag]：=resolve（head、left of root、flag）またはsolve（head、right of root、flag）

  を返します。

• メインメソッドからsolve（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