Danh Sách Liên Kết Trong Cây Nhị Phân Trong C++

Giả sử chúng ta có cây nhị phân root và danh sách liên kết với head là nút đầu. Trả về true nếu tất cả các phần tử trong danh sách liên kết từ head tương ứng với một đường đi xuống (downward path) trong cây nhị phân, ngược lại false.

Ví dụ cây như hình, danh sách [1,4,2,6] → true.

Để giải quyết, chúng ta làm theo các bước:

Định nghĩa map dp để memoization.
Định nghĩa solve(head, root, flag): nếu head null trả về true; nếu root null trả về false.
Nếu dp đã có kết quả cho (head, root, flag) thì trả về.
Nếu head->val == root->val: ret = solve(head->next, root->left, false) || solve(head->next, root->right, false); nếu ret true thì dp[...]=true; ngược lại dp[...] = solve(head, root->left, flag) || solve(head, root->right, flag).
Ngược lại nếu !flag trả về false; ngược lại dp[...] = solve(head, root->left, flag) || solve(head, root->right, flag).
Từ main: gọi solve(head, root, true).

Ví dụ (C++)

Hãy xem 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);
    }
};

int 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]

Danh Sách Liên Kết Trong Cây Nhị Phân Trong C++

Ví dụ (C++)

Đầu vào

Đầu ra