JD 1520:树的子结构

2024-09-07 03:18
文章标签 子结构 jd 1520

本文主要是介绍JD 1520:树的子结构,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

OJ题目:click here~~

剑指offer 面试题18

AC_CODE

const int maxn = 1008 ;
const int maxm = 1008 ;
int m , n ;
struct Node{int x ;int l ;int r ;Node():l(-1),r(-1){}
}A[maxn] , B[maxm];vector<int> g ;
void Findroot(int k){if(A[k].x == B[1].x) g.push_back(k) ;if(A[k].l != -1) Findroot(A[k].l) ;if(A[k].r != -1) Findroot(A[k].r) ;
}
bool f ;
void judge(int k , int kk){if(A[k].x != B[kk].x) f = false ;if(A[k].l == -1 && B[kk].l != -1) f = false ;if(A[k].r == -1 && B[kk].r != -1) f = false ;if(A[k].l != -1 && B[kk].l != -1) judge(A[k].l , B[kk].l) ;if(A[k].r != -1 && B[kk].r != -1) judge(A[k].r , B[kk].r) ;
}int main(){//freopen("in.txt" , "r" , stdin) ;while(scanf("%d%d",&n,&m) != EOF){if(m == 0) puts("NO") ;if(n < m) puts("NO") ;int i , j , num , l , r ;for(i = 0;i < maxn;i++){A[i] = Node() ;B[i] = Node() ;}for(i = 1;i <= n;i++) scanf("%d",&A[i].x) ;for(i = 1;i <= n;i++){scanf("%d",&num) ;if(num == 1)scanf("%d" , &A[i].l) ;if(num == 2)scanf("%d%d",&A[i].l,&A[i].r) ;}for(i = 1;i <= m;i++) scanf("%d",&B[i].x) ;for(i = 1;i <= m;i++){scanf("%d",&num) ;if(num == 1)scanf("%d",&B[i].l) ;if(num == 2)scanf("%d%d",&B[i].l , &B[i].r) ;}if(m == 0 || n < m) continue ;g.clear() ;Findroot(1) ;bool ans = false ;for(i = 0;i < g.size();i++){f = true ;judge(g[i] , 1) ;ans |= f ;if(ans) break ;}if(ans) puts("YES") ;else puts("NO") ;}return 0 ;
}


这篇关于JD 1520:树的子结构的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1143901

相关文章

JD 1474:矩阵幂

OJ题目:click here~~ 题目分析:经典题目,矩阵快速幂。 typedef vector<int> vec ;typedef vector<vec> mat ;int n ;mat mul(mat &A , mat &B){mat C(n , vec(n)) ;for(int i = 0;i < n;i++)for(int j = 0;j < n;j++)for(int k

JD 1497:面积最大的全1子矩阵

OJ题目:click here~~ 题目分析:经典题目。。 const int maxn = 1008 ;int n , m ;int x[maxn][maxn] ;int h[maxn] , Left[maxn] , Right[maxn] ;void check(int &a , int b){if(b > a) a = b ;}void all_1_matrix()

JD 1147:Jugs(一种用最少步骤求解的方法)

OJ题目:click here~~ 题目分析:九度上这道没有要求最少步数,只要得到最后结果即可AC , bfs , dfs都行。最少步骤的方法肯定也能AC啦,分析如下。 输入的三个数:a,b,n;> 由题不定方程ax+by=n必定有解> 如果b=n,则fill B即可,否则用试探法求出这样的两组解(a1,b1)及(a2,b2),其中a1 >0,b1<0;a1是满足方程的最小正整数;a2

JD 1204:农夫、羊、菜和狼的故事

OJ题目:click here~~ #define vegetable_go 0#define vegetable_come 1#define sheep_go 2#define sheep_come 3#define wolf_go 4#define wolf_come 5#define nothing_go 6#define nothing_come 7using

JD 1027:欧拉回路

OJ题目:click here~~ 题目分析: 若图G中存在这样一条路径,使得它恰通过G中每条边一次,则称该路径为欧拉路径。若该路径是一个圈,则称为欧拉(Euler)回路。 具有欧拉路径的图称为欧拉图(简称E图)。 无向图存在欧拉回路的充要条件: 一个无向图存在欧拉回路,当且仅当该图拥有奇数度数的顶点的个数为0且该图是连通图。 有向图存在欧拉回路的充要条件: 一

JD 1008:最短路径问题

OJ题目:click here~~ 题目分析:无向图,每条边有长度和花费,求点s到t的最短路径长度和花费。若有相同的最短路径长度,找出最少的花费的那条。 邻接表 + Dijstra + 优先队列 AC_CODE const int maxn = 1008 ;const int inf = 1<<30 ;vector<int> g[maxn] ;int len[maxn][maxn

JD 1521:二叉树的镜像

OJ题目:click here~~ 题目分析:给一棵二叉树,输出镜像的前序遍历序列 二叉树的镜像的前序遍历序列 = 对原二叉树进行根 右 左 的遍历。 剑指offer 面试题19 AC_CODE const int maxn = 1008 ;LL x[maxn] ;int n ;struct Node{int x ;int l ;int r ;Node():l(-1),r(-1

JD 1368:二叉树中和为某一值的路径

OJ题目:click here~~ 题目分析:找二叉树中和为某一值的路径。。。 剑指offer 面试题25 AC_CODE const int maxn = 10008 ;int n , k ;struct Node{int x ;int l , r ;Node():l(-1),r(-1){}}tree[maxn];void FindPath(int t , int sum ,

JD 1385:重建二叉树

OJ题目:click here~~ 题目分析:给前序遍历序列和中序遍历序列,重构二叉树并输出后序遍历序列 剑指offer 面试题6 AC_CODE int pre[1008] , in[1008] ;struct Node{int x ;Node *left ;Node *right ;};bool buildsubtree(Node*& root , int* spre , in

剑指offer:树的子结构(Python)

题目描述 输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构) # -*- coding:utf-8 -*-# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = None