给定彼此独立的两棵二叉树,判断 t1 树是否有与 t2 树拓扑结构完全相同的子树。
设 t1 树的边集为 E1,t2 树的边集为 E2,若 E2 等于 E1 ,则表示 t1 树和t2 树的拓扑结构完全相同。
第一行输入两个整数 n 和 root,n 表示二叉树 t1 的总节点个数,root 表示二叉树 t1 的根节点。
以下 n 行每行三个整数 fa,lch,rch,表示 fa 的左儿子为 lch,右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子,rch同理)
第 n+2 行输入两个整数 m 和 root,n 表示二叉树 t2 的总节点个数,root 表示二叉树 t2 的根节点。
以下 m 行每行三个整数 fa,lch,rch,表示 fa 的左儿子为 lch,右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子,rch同理)
如果 t1 树有与 t2 树拓扑结构完全相同的子树,则输出 "true",否则输出 "false"。
9 1 1 2 3 2 4 5 4 0 8 8 0 0 5 9 0 9 0 0 3 6 7 6 0 0 7 0 0 5 2 2 4 5 4 0 8 8 0 0 5 9 0 9 0 0
true
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.HashMap; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 构建树A String[] params = br.readLine().split(" "); int n = Integer.parseInt(params[0]); TreeNode treeA = new TreeNode(Integer.parseInt(params[1])); HashMap<Integer, TreeNode> map = new HashMap<>(); map.put(treeA.val, treeA); for(int i = 0; i < n; i++){ params = br.readLine().split(" "); int val = Integer.parseInt(params[0]); int leftVal = Integer.parseInt(params[1]); int rightVal = Integer.parseInt(params[2]); TreeNode node = map.get(val); if(leftVal != 0) { node.left = new TreeNode(leftVal); map.put(leftVal, node.left); } if(rightVal != 0) { node.right = new TreeNode(rightVal); map.put(rightVal, node.right); } } // 构建树B params = br.readLine().split(" "); int m = Integer.parseInt(params[0]); TreeNode treeB = new TreeNode(Integer.parseInt(params[1])); map.clear(); map.put(treeB.val, treeB); for(int i = 0; i < m; i++){ params = br.readLine().split(" "); int val = Integer.parseInt(params[0]); int leftVal = Integer.parseInt(params[1]); int rightVal = Integer.parseInt(params[2]); TreeNode node = map.get(val); if(leftVal != 0) { node.left = new TreeNode(leftVal); map.put(leftVal, node.left); } if(rightVal != 0) { node.right = new TreeNode(rightVal); map.put(rightVal, node.right); } } System.out.println(isSubStructure(treeA, treeB)); } private static boolean isSubStructure(TreeNode treeA, TreeNode treeB) { if(treeA == null || treeB == null) return false; // 空树不是任何一棵树的子树 // 树A和树B完全一样,或树B为树A的左右子树之一都可以 return isSame(treeA, treeB) || isSubStructure(treeA.left, treeB) || isSubStructure(treeA.right, treeB); } private static boolean isSame(TreeNode treeA, TreeNode treeB) { if(treeB == null) return true; // B树到空,说明节点都检查完了,返回true if(treeA == null || treeA.val != treeB.val) return false; // A树为空或节点值不同,返回false // 检查两棵树的左右子树是否都相同 return isSame(treeA.left, treeB.left) && isSame(treeA.right, treeB.right); } } class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int val) { this.val = val; } }
#include<bits/stdc++.h> using namespace std; bool judge(int root1,int root2,int* lc1,int* rc1,int* lc2,int* rc2) { if(!root2 && !root1) return true; if(!root1 || !root2 || (root1!=root2)) return false; return judge(lc1[root1],lc2[root2],lc1,rc1,lc2,rc2) && judge(rc1[root1],rc2[root2],lc1,rc1,lc2,rc2); } bool visit(int root1,int root2,int* lc1,int* rc1,int* lc2,int* rc2) { if(!root2 && !root1) return true; if(!root1 || !root2) return false; return judge(root1,root2,lc1,rc1,lc2,rc2) || visit(lc1[root1],root2,lc1,rc1,lc2,rc2) || visit(rc1[root1],root2,lc1,rc1,lc2,rc2); } int main() { int n,root1; cin>>n>>root1; int p; int* lc1 = new int[n+1]; int* rc1 = new int[n+1]; for(int i=0;i<n;++i) { cin>>p; cin>>lc1[p]>>rc1[p]; } int m,root2; cin>>m>>root2; if(m>n) { cout<<"false"; return 0; } int* lc2 = new int[n+1]; int* rc2 = new int[n+1]; for(int j=0;j<m;++j) { cin>>p; cin>>lc2[p]>>rc2[p]; } bool ans = visit(root1,root2,lc1,rc1,lc2,rc2); if(ans) cout<<"true"; else cout<<"false"; return 0; }
//使用结构体存树 #include <iostream> #include <cstdio> #include <cstring> using namespace std; const int N = 1000010; int n,m,k,q; struct Edge{ int l,r; }edges[N]; int main() { cin>>n>>m; while(n -- ) { int a,b,c; cin>>a>>b>>c; edges[a] = {b,c}; } cin>>k>>q; int t=0; for(int l =0 ;l < k; l++) { int a,b,c; cin>>a>>b>>c; if(edges[a].l==b) t++; if(edges[a].r==c) t++; } if(t != k*2) puts("false"); else puts("true"); return 0; } //树是特殊的图 //邻接矩阵 最多能存 1000*1000个数据,明显不够 //所以可以用邻接表存 #include <iostream> #include <cstdio> #include <cstring> using namespace std; const int N = 1000010; int n,m,k,q; int h[N],e[N],ne[N],idx; void add(int a,int b){ e[idx] = b,ne[idx] = h[a],h[a] = idx++; } int main() { memset(h, -1, sizeof h); cin>>n>>m; while(n -- ) { int a,b,c; cin>>a>>b>>c; add(a,b); add(a,c); } cin>>k>>q; int t=0; for(int l =0 ;l < k; l++) { int a,b,c; cin>>a>>b>>c; for(int i = h[a]; ~i ; i = ne[i]) { int j=e[i]; if(j == b || j == c) t++; } } if(t != k*2) puts("false"); else puts("true"); return 0; }
#include <stdio.h> #include <stdlib.h> typedef int ID; typedef struct TreeNode { ID id; struct TreeNode* left; struct TreeNode* right; } TreeNode, *PTreeNode, *BT; typedef struct { ID parent, l_child, r_child; } TreeNodeInfo, *Infos; BT buildTree(Infos infos, ID id) { if (id == 0) return NULL; BT root = (PTreeNode) malloc(sizeof(TreeNode)); if (!root) return NULL; root->id = id; root->left = buildTree(infos, (*(infos + id)).l_child); root->right = buildTree(infos, (*(infos + id)).r_child); return root; } void preorder(BT root) { if (!root) return; fprintf(stdout, "%d ", root->id); preorder(root->left); preorder(root->right); } int isSameTree(BT A, BT B) { if (!A || !B) return A == B; return A->id == B->id && isSameTree(A->left, B->left) && isSameTree(A->right, B->right); } int chkIdentical(BT A, BT B) { if (!A) return 0; return isSameTree(A, B) || chkIdentical(A->left, B) || chkIdentical(A->right, B); } int main(const int argc, const char* const argv[]) { int n, m, root_1_id, root_2_id; int fa, l_ch, r_ch; fscanf(stdin, "%d %d", &n, &root_1_id); TreeNodeInfo root_1_infos[n + 1]; int x = n; while (x--) { fscanf(stdin, "%d %d %d", &fa, &l_ch, &r_ch); (*(root_1_infos + fa)).l_child = l_ch; (*(root_1_infos + fa)).r_child = r_ch; } fscanf(stdin, "%d %d", &m, &root_2_id); TreeNodeInfo root_2_infos[n + 1]; while (m--) { fscanf(stdin, "%d %d %d", &fa, &l_ch, &r_ch); (*(root_2_infos + fa)).l_child = l_ch; (*(root_2_infos + fa)).r_child = r_ch; } BT root_1 = buildTree(root_1_infos, root_1_id), root_2 = buildTree(root_2_infos, root_2_id); // preorder(root_1), fputc(10, stdout), preorder(root_2); return fprintf(stdout, "%s", chkIdentical(root_1, root_2) ? "true" : "false"), 0; }
int n=Integer.parseInt(sc.nextLine().split(" ")[0]); StringBuilder nString=new StringBuilder(); for (int i = 0; i < n; i++) { nString.append(sc.nextLine()+" "); } int m=Integer.parseInt(sc.nextLine().split(" ")[0]); StringBuilder mString=new StringBuilder(); for (int i = 0; i < m; i++) { mString.append(sc.nextLine()+" "); } String Sn=nString.toString(); String Sm = mString.toString(); System.out.println(Sm.contains(Sn)||Sn.contains(Sm));