历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

路径刷题整理

作者：

Esenhowerstudyharder , 2024-12-10 09:25:54 , 所有人可见 , 阅读 10

ab路径


#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
vector<int>path;vector<int>path1;vector<int>path2;int T;
struct TreeNode{
    int data;
    TreeNode*left;# ab路径

include[HTML_REMOVED]

using namespace std;
vector[HTML_REMOVED]path;vector[HTML_REMOVED]path1;vector[HTML_REMOVED]path2;int T;
struct TreeNode{
int data;
TreeNodeleft;
TreeNoderight;
};
TreeNode CreateTree(){
int k;
scanf(“%d”,&k);
if(k==0)return nullptr;
TreeNoderoot=new TreeNode;
root->data=k;
root->left=CreateTree();
root->right=CreateTree();
return root;
}
void dfs(TreeNoderoot,int n,int m){
if(!root)return;
path.push_back(root->data);
if(root->data==n)path1=path;
if(root->data==m)path2=path;
dfs(root->left,n,m);
dfs(root->right,n,m);
path.pop_back();
}
void fet_path(vector[HTML_REMOVED]A,vector[HTML_REMOVED]B){
int i=0;
while(A[i]==B[i]&&i<=A.size()-1&&i<=B.size()-1)i++; i–;
printf(“%d\n”,A.size()+B.size()-2-2i);
for(int j=A.size()-1;j>i;j–)printf(“%d “,A[j]);
for(int j=i;j[HTML_REMOVED]>a>>b;
dfs(root,a,b);
fet_path(path1,path2);
}
return 0;
}

#根叶和k

include[HTML_REMOVED]

using namespace std;
struct TreeNode{
int data;
TreeNodeleft;
TreeNoderight;
};
TreeNode CreateTree(){
int k;
scanf(“%d”,&k);
if(k==0)return nullptr;
TreeNoderoot=new TreeNode;
root->data=k;
root->left=CreateTree();
root->right=CreateTree();
return root;
}
vector[HTML_REMOVED]>ans;vector[HTML_REMOVED]path;
int cnt=0;
void dfs(TreeNode*root,int sum){
if(!root)return;
sum-=root->data;
path.push_back(root->data);

if(!root->left&&!root->right&&!sum){cnt++;ans.push_back(path);}

dfs(root->left,sum);
dfs(root->right,sum);

path.pop_back();

}
int main(){
TreeNode*root=CreateTree();
int k;
scanf(“%d”,&k);
dfs(root,k);
if(cnt){
printf(“%d\n”,cnt);
for(auto c:ans){
for(auto d:c)
printf(“%d “,d);
puts(“”);
}
}
else cout<<0<<endl;
return 0;
}

#最大根叶和

include[HTML_REMOVED]

using namespace std;
struct TreeNode{
int data;
TreeNodeleft;
TreeNoderight;
};
TreeNode CreateTree(){
int k;
scanf(“%d”,&k);
if(k==0)return nullptr;
TreeNoderoot=new TreeNode;
root->data=k;
root->left=CreateTree();
root->right=CreateTree();
return root;
}
int maxn=0;vector[HTML_REMOVED]ans;vector[HTML_REMOVED]path;
void dfs(TreeNode*root,int sum){
if(!root)return;
sum+=root->data;
path.push_back(root->data);

if(!root->left&&!root->right&&sum>maxn){maxn=sum;ans=path;}
dfs(root->left,sum);
dfs(root->right,sum);

path.pop_back();

}
int main(){
TreeNode*root=CreateTree();
dfs(root,0);
printf(“%d\n”,maxn);
for(auto c:ans)
printf(“%d “,c);
return 0;
}

二叉树两个结点路径长度

include [HTML_REMOVED]

using namespace std;
const int N=1010;
int l[N],r[N];
int p[N],dist[N];
int n,m;
void dfs(int u,int d){
dist[u]=d;
if(l[u]!=-1)dfs(l[u],d+1);
if(r[u]!=-1)dfs(r[u],d+1);
}
int get_lca(int a,int b){
if(dist[a]>dist[b])swap(a,b);
while(dist[b]>dist[a])b=p[b];
while(a!=b)a=p[a],b=p[b];
return a;
}
int main()
{ int T;
scanf(“%d”,&T);
while(T–){
scanf(“%d%d”,&n,&m);
memset(l,-1,sizeof l);
memset(r,-1,sizeof r);
for(int i=1;i<=n;i++){
int a,b;
scanf(“%d%d”,&a,&b);
l[i]=a,r[i]=b;
if(a!=-1)p[a]=i;
if(b!=-1)p[b]=i;
}
dfs(1,0);//预处理
while(m–){
int a,b;
scanf(“%d%d”, &a, &b);

        int lca=get_lca(a,b);
        printf("%d\n",dist[a]+dist[b]-2*dist[lca]);
    }
}

return 0;

}
路径和为k

class Solution {
public: unordered_map<long long,long long>cnt;
        int ans=0;
    void dfs(TreeNode*root,int targetSum,long long cur){
        if(!root)return;
        cur+=root->val;
        ans+=cnt[cur-targetSum];
        cnt[cur]++;
        dfs(root->left,targetSum,cur);
        dfs(root->right,targetSum,cur);
        cnt[cur]--;
    }
    int pathSum(TreeNode* root, int targetSum) {
        cnt[0]=1;
        if(root)dfs(root,targetSum,0);
        return ans; 
    }
};

#根叶不足结点
给你二叉树的根节点 root 和一个整数 limit ，请你同时删除树中所有 不足节点 ，并返回最终二叉树的根节点。

假如通过节点 node 的每种可能的 “根-叶” 路径上值的总和全都小于给定的 limit，则该节点被称之为 不足节点 ，需要被删除。

class Solution {
public:
TreeNode sufficientSubset(TreeNode root, int limit) {
dfs(root, 0, limit);
return root;
}

void dfs(TreeNode* &root, int sum, int limit) {
    sum += root->val;
    if (!root->left && !root->right) {
        if (sum < limit) root = NULL;
    } else {
        if (root->left) dfs(root->left, sum, limit);
        if (root->right) dfs(root->right, sum, limit);
        if (!root->left && !root->right) root = NULL;
    }
}

};
string path, paths, pathd;
void dfs(TreeNode* root, int s, int d) {
if(root->val == s) paths = path;
if(root->val == d) pathd = path;

    if(root->left) path += 'L', dfs(root->left, s, d), path.pop_back(); 
    if(root->right) path += 'R', dfs(root->right, s, d), path.pop_back();
}
string getDirections(TreeNode* root, int s, int d) {
    dfs(root, s, d);
    int i = 0, j = 0;
    while(paths[i] == pathd[j]) i++, j++;
    return string(paths.size() - i, 'U') + pathd.substr(j);
}

#最长交错路径

class Solution {
int ans=0;
void dfs(TreeNode root,int dir,int dis){//(当前结点，左/右孩子，路径长度)
if(!root)return;//空结点返回
ans=max(ans,dis);//更新最大值
if(dir){//如果当前结点是其父结点的右孩子
dfs(root->left,0,dis+1);//搜索其左孩子时，满足ZigZig，路径长度+1
dfs(root->right,1,1);//搜索其右孩子时，不满足ZigZig，路径长度置为1
}
else{//如果当前结点是其父结点的左孩子
dfs(root->left,0,1);//搜索其左孩子时，不满足ZigZig，路径长度置为1
dfs(root->right,1,dis+1);//搜索其右孩子时，满足ZigZig，路径长度+1
}
}
public:
int longestZigZag(TreeNode root) {
dfs(root->left,0,1);//0左节点
dfs(root->right,1,1);//1右结点
return ans;
}
};

    TreeNode*right;
};
TreeNode* CreateTree(){
    int k;
    scanf("%d",&k);
    if(k==0)return nullptr;
    TreeNode*root=new TreeNode;
    root->data=k;
    root->left=CreateTree();
    root->right=CreateTree();
    return root;
}
void dfs(TreeNode*root,int n,int m){
    if(!root)return;
    path.push_back(root->data);
    if(root->data==n)path1=path;
    if(root->data==m)path2=path;
    dfs(root->left,n,m);
    dfs(root->right,n,m);
    path.pop_back();
}
void fet_path(vector<int>A,vector<int>B){
    int i=0;
    while(A[i]==B[i]&&i<=A.size()-1&&i<=B.size()-1)i++;    i--;
    printf("%d\n",A.size()+B.size()-2-2*i);
    for(int j=A.size()-1;j>i;j--)printf("%d ",A[j]);
    for(int j=i;j<B.size();j++)printf("%d ",B[j]);
    puts("");
}
int main(){
    TreeNode*root=CreateTree();
    scanf("%d",&T);
    while(T--){
        int a,b;
        cin>>a>>b;
        dfs(root,a,b);
        fet_path(path1,path2);
    }
    return 0; 
}

根叶和k

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
struct TreeNode{
    int data;
    TreeNode*left;
    TreeNode*right;
};
TreeNode* CreateTree(){
    int k;
    scanf("%d",&k);
    if(k==0)return nullptr;
    TreeNode*root=new TreeNode;
    root->data=k;
    root->left=CreateTree();
    root->right=CreateTree();
    return root;
}
vector<vector<int>>ans;vector<int>path;
int cnt=0;
void dfs(TreeNode*root,int sum){
    if(!root)return;
    sum-=root->data;
    path.push_back(root->data);

    if(!root->left&&!root->right&&!sum){cnt++;ans.push_back(path);}

    dfs(root->left,sum);
    dfs(root->right,sum);

    path.pop_back();
}
int main(){
    TreeNode*root=CreateTree();
    int k;
    scanf("%d",&k);
    dfs(root,k);
    if(cnt){
        printf("%d\n",cnt);
        for(auto c:ans){
            for(auto d:c)
            printf("%d ",d);
            puts("");
        }
    }
    else cout<<0<<endl;
    return 0; 
}

最大根叶和


#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
struct TreeNode{
    int data;
    TreeNode*left;
    TreeNode*right;
};
TreeNode* CreateTree(){
    int k;
    scanf("%d",&k);
    if(k==0)return nullptr;
    TreeNode*root=new TreeNode;
    root->data=k;
    root->left=CreateTree();
    root->right=CreateTree();
    return root;
}
int maxn=0;vector<int>ans;vector<int>path;
void dfs(TreeNode*root,int sum){
    if(!root)return;
    sum+=root->data;
    path.push_back(root->data);

    if(!root->left&&!root->right&&sum>maxn){maxn=sum;ans=path;}
    dfs(root->left,sum);
    dfs(root->right,sum);

    path.pop_back();
}
int main(){
    TreeNode*root=CreateTree();
    dfs(root,0);
    printf("%d\n",maxn);
    for(auto c:ans)
    printf("%d ",c);
    return 0; 
}
#二叉树两个结点路径长度
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1010;
int l[N],r[N];
int p[N],dist[N];
int n,m;
void dfs(int u,int d){
    dist[u]=d;
    if(l[u]!=-1)dfs(l[u],d+1);
    if(r[u]!=-1)dfs(r[u],d+1);
}
int get_lca(int a,int b){
    if(dist[a]>dist[b])swap(a,b);
    while(dist[b]>dist[a])b=p[b];
    while(a!=b)a=p[a],b=p[b];
    return a;
}
int main()
{   int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        memset(l,-1,sizeof l);
        memset(r,-1,sizeof r);
        for(int i=1;i<=n;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            l[i]=a,r[i]=b;
            if(a!=-1)p[a]=i;
            if(b!=-1)p[b]=i;
        } 
        dfs(1,0);//预处理
        while(m--){
            int a,b;
            scanf("%d%d", &a, &b);

            int lca=get_lca(a,b);
            printf("%d\n",dist[a]+dist[b]-2*dist[lca]);
        }
    }

    return 0;
}
路径和为k

class Solution {
public: unordered_map[HTML_REMOVED]cnt;
int ans=0;
void dfs(TreeNoderoot,int targetSum,long long cur){
if(!root)return;
cur+=root->val;
ans+=cnt[cur-targetSum];
cnt[cur]++;
dfs(root->left,targetSum,cur);
dfs(root->right,targetSum,cur);
cnt[cur]–;
}
int pathSum(TreeNode root, int targetSum) {
cnt[0]=1;
if(root)dfs(root,targetSum,0);
return ans;
}
};

根叶不足结点

给你二叉树的根节点 root 和一个整数 limit ，请你同时删除树中所有不足节点，并返回最终二叉树的根节点。

假如通过节点 node 的每种可能的 “根-叶” 路径上值的总和全都小于给定的 limit，则该节点被称之为不足节点，需要被删除。

class Solution {
public:
    TreeNode* sufficientSubset(TreeNode* root, int limit) {
        dfs(root, 0, limit);
        return root;
    }

    void dfs(TreeNode* &root, int sum, int limit) {
        sum += root->val;
        if (!root->left && !root->right) {
            if (sum < limit) root = NULL;
        } else {
            if (root->left) dfs(root->left, sum, limit);
            if (root->right) dfs(root->right, sum, limit);
            if (!root->left && !root->right) root = NULL;
        }
    }
};
 string path, paths, pathd;
    void dfs(TreeNode* root, int s, int d) {
        if(root->val == s) paths = path;
        if(root->val == d) pathd = path;

        if(root->left) path += 'L', dfs(root->left, s, d), path.pop_back(); 
        if(root->right) path += 'R', dfs(root->right, s, d), path.pop_back();
    }
    string getDirections(TreeNode* root, int s, int d) {
        dfs(root, s, d);
        int i = 0, j = 0;
        while(paths[i] == pathd[j]) i++, j++;
        return string(paths.size() - i, 'U') + pathd.substr(j);
    }

最长交错路径

class Solution {
    int ans=0;
    void dfs(TreeNode* root,int dir,int dis){//(当前结点，左/右孩子，路径长度)
        if(!root)return;//空结点返回
        ans=max(ans,dis);//更新最大值
        if(dir){//如果当前结点是其父结点的右孩子
            dfs(root->left,0,dis+1);//搜索其左孩子时，满足ZigZig，路径长度+1
            dfs(root->right,1,1);//搜索其右孩子时，不满足ZigZig，路径长度置为1
        } 
        else{//如果当前结点是其父结点的左孩子
            dfs(root->left,0,1);//搜索其左孩子时，不满足ZigZig，路径长度置为1
            dfs(root->right,1,dis+1);//搜索其右孩子时，满足ZigZig，路径长度+1
        }       
    }
public:
    int longestZigZag(TreeNode* root) {
        dfs(root->left,0,1);//0左节点
        dfs(root->right,1,1);//1右结点
        return ans;
    }
};

0 评论

App 内打开