資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中二叉樹中的連結串列
假設我們有一個二叉樹根節點和一個以頭部作為第一個節點的連結串列。如果從頭部開始的連結串列中的所有元素都對應於二叉樹中連線的一些向下路徑，則我們必須返回 True，否則返回 False。因此，如果樹如下所示：
並且連結串列是 [1,4,2,6]，則輸出將為 true。
為了解決這個問題，我們將遵循以下步驟：
定義一個對映 dp
定義一個名為 solve() 的方法，它將接收頭部、根節點和標誌
如果頭部為空，則返回 true，或者如果根節點為空，則返回 false
如果 dp 中包含頭部，並且 dp[head] 中包含根節點，並且 dp[head, root] 中包含標誌，則返回 dp[head, root, flag]
如果 head 的值等於 root 的值，則
ret := solve(head 的下一個節點, root 的左子節點, false) 或 solve(head 的下一個節點, root 的右子節點, false)
如果 ret 被設定，則 dp[head, root, flag] := true 並返回 dp[head, root, flag]
dp[head, root, flag] = solve(head, root 的左子節點, flag) 或 solve(head, root 的右子節點, flag)
返回 dp[head, root, flag]
否則，當標誌未設定時，返回 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]
輸出
1
2K+ 次檢視
