C++ 이진 트리의 연결 목록

이진 트리 루트와 첫 번째 노드로 헤드가 있는 연결 목록이 있다고 가정합니다. 헤드에서 시작하는 연결 목록의 모든 요소가 이진 트리에 연결된 일부 하향 경로에 해당하면 True를 반환해야 하고 그렇지 않으면 False를 반환해야 합니다. 트리가 다음과 같다면 -

C++ 이진 트리의 연결 목록

그리고 연결 리스트가 [1,4,2,6]이면 출력은 참이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

지도 정의 dp
solve()라는 메서드를 정의합니다. 이것은 head, root 및 flag를 사용합니다.
헤드가 null이면 true를 반환하고, root가 null이면 false를 반환합니다.
dp에 헤드가 있고 dp[head]에 루트가 있고 dp[head, root]에 플래그가 있으면 dp[head, root, flag]
를 반환합니다.
헤드 값 =루트 값이면
- ret :=solve(head의 다음, root의 왼쪽, false) 또는 solve(head의 다음, root의 오른쪽, false)
- ret가 설정되면 dp[head, root, flag] :=true를 반환하고 dp[head, root, flag]
  를 반환합니다.
- dp[헤드, 루트, 플래그] =해결(헤드, 루트의 왼쪽, 플래그) 또는 해결(헤드, 루트의 오른쪽, 플래그)
- 반환 dp[헤드, 루트, 플래그]
그렇지 않으면 플래그가 설정되지 않은 경우 dp[head, root, flag]를 반환합니다. :=false
그렇지 않으면 dp[head, root, flag]를 반환합니다. :=solve(head, root의 왼쪽, flag) 또는 solve(head, 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]