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

[编程题]判断t1树是否包含t2树全部的拓扑结构

热度指数：1104 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定彼此独立的两棵二叉树，判断 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"。

示例1

输入

输出

true

备注:

算法知识视频讲解

勇敢牛牛，不怕困难！

#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;
}

发表于 2021-07-24 18:38:36 回复(0)