本文主要是介绍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:树的子结构的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!