判断t1树是否包含t2树全部的拓扑结构

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    public static int n, m , root1, root2;
    public static Node[] nodes1, nodes2;

    public static class Node {
        int val, left, right;
        Node(int val, int left, int right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static boolean contain(int index1, int index2) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(index2);
        while (!queue.isEmpty()) {
            int front = queue.poll();
            int left1 = nodes1[front].left;
            int right1 = nodes1[front].right;
            int left2 = nodes2[front].left;
            int right2 = nodes2[front].right;
            if (left2 != 0) {
                if (left1 != left2) return false;
                queue.offer(left2);
            }
            if (right2 != 0) {
                if (right1 != right2) return false;
                queue.offer(right2);
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        n = input.nextInt();
        root1 = input.nextInt();
        nodes1 = new Node[n+1];
        for (int i = 0; i < n; i++) {
            int val = input.nextInt();
            int left = input.nextInt();
            int right = input.nextInt();
            nodes1[val] = new Node(val, left, right);
        }
        m = input.nextInt();
        root2 = input.nextInt();
        nodes2 = new Node[n+1];
        boolean flag = false;
        for (int i = 0; i < m; i++) {
            int val = input.nextInt();
            flag = val > n;
            int left = input.nextInt();
            int right = input.nextInt();
            nodes2[val] = new Node(val, left, right);
        }
        if (flag) {
            System.out.println(false);
            return;
        }
        System.out.println(contain(root1, root2));
    }
}

#include <iostream>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(NULL), right(NULL) {}
}; 

void createTree(TreeNode* root, int& n) {
    if(root == nullptr)
        return ;
    int rootVal, leftVal, rightVal;
    cin >> rootVal >> leftVal >> rightVal;
    if(leftVal != 0) {
        TreeNode* leftNode = new TreeNode(leftVal);
        leftNode->left = leftNode->right = nullptr;
        root->left = leftNode;
        createTree(leftNode, --n);
    }
    if(rightVal != 0) {
        TreeNode* rightNode = new TreeNode(rightVal);
        rightNode->left = rightNode->right = nullptr;
        root->right = rightNode;
        createTree(rightNode, --n);
    }
    return ;
}

bool isSametree(TreeNode* root, TreeNode* subRoot) {
        if(subRoot == nullptr)
            return true;
        if(root == nullptr)
            return false;
        if(root->val != subRoot->val)
            return false;
        bool inside = isSametree(root->left, subRoot->left);
        bool outside = isSametree(root->right, subRoot->right);
        return inside && outside;
    }

bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if(subRoot == nullptr)
            return true;
        if(root == nullptr)
            return false;
        return isSametree(root, subRoot) || isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
    }


int main() {
    int n1, rootVal1;
    cin >> n1 >> rootVal1;
    TreeNode* rootA = new TreeNode(rootVal1);
    rootA->left = rootA->right = nullptr;
    createTree(rootA, n1);
    
    int n2, rootVal2;
    cin >> n2 >> rootVal2;
    TreeNode* rootB = new TreeNode(rootVal2);
    rootB->left = rootB->right = nullptr;
    createTree(rootB, n2);
    if(isSubtree(rootA, rootB))
        cout << "true";
    else
        cout << "false";
    return 0;
}

#include <stdio.h>
#include <stdlib.h>

typedef struct {
  int parent, l_child, r_child;
} TreeNodeInfo, *Infos;

int judge(Infos A, Infos B, int a_id, int b_id) { // judge B树是否是A树的子集
  if (!a_id && !b_id) return 1;
  if (!a_id) return 0;
  if (!b_id) return 1;
  return a_id == b_id
    && judge(A, B, A[a_id].l_child, B[a_id].l_child)
    && judge(A, B, A[a_id].r_child, B[a_id].r_child);
}

int isSubStructure(Infos A, Infos B, int a_id, int b_id) {
  if (!a_id) return 0;
  return judge(A, B, a_id, b_id)
    || isSubStructure(A, B, A[a_id].l_child, b_id)
    || isSubStructure(A, B, A[a_id].r_child, b_id);
}

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 root1[n + 1];
  int x = n;
  while (x--) {
    fscanf(stdin, "%d %d %d", &fa, &l_ch, &r_ch);
    (*(root1 + fa)).l_child = l_ch;
    (*(root1 + fa)).r_child = r_ch;
  }
  
  fscanf(stdin, "%d %d", &m, &root_2_id);
  TreeNodeInfo root2[n + 1];
  while (m--) {
    fscanf(stdin, "%d %d %d", &fa, &l_ch, &r_ch);
    (*(root2 + fa)).l_child = l_ch;
    (*(root2 + fa)).r_child = r_ch;
  }
  
  printf("%s", isSubStructure(root1, root2, root_1_id, root_2_id) ? "true" : "false");
  return 0;
}

#数据的输入处理
#树1
n, r1 = list(map(int, input().split()))
#将树定义为字典
tree1 = {}
for _ in range(n):
    x, left, right = list(map(int, input().split()))
    #以元祖的形式定义子树
    tree1[x] = (left, right)
#树2
m, r2 = list(map(int, input().split()))
tree2 = {}
for _ in range(m):
    x, left, right = list(map(int, input().split()))
    tree2[x] = (left, right)
    
# ==============================
#检查x,以及它作为根时的子树是否在tree 1里面
def checkNode(x) -> bool: 
    if not x in tree1:
        return False
    #取出子树
    l2, r2 = tree2[x]
    #如果子树非空，但是不在树1中
    if l2 and l2 not in tree1[x]:
        return False
    if r2 and r2 not in tree1[x]:
        return False
    return True
# 遍历tree 2， 查每个节点和它左右的链接
def bfs(tree, root): 
    queue = [root]
    #层次遍历
    while queue:
        x = queue.pop()
        if not checkNode(x):
            return False
 
        if tree[x][0]: # left
            queue.append(tree[x][0])
        if tree[x][1]: # right
            queue.append(tree[x][1])
    
    return True

if bfs(tree2, r2):
    print('true')
else:
    print('false')
    
    

#include<bits/stdc++.h>
using namespace std;
bool judge(int root1,int root2,int* lc1,int* rc1,int* lc2,int* rc2)
{
    if(!root2) return true;
    if((!root1) || (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) return true;
    if(!root1) 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;

}