判断t1树中是否有与t2树拓扑结构完全相同的子树

[编程题]判断t1树中是否有与t2树拓扑结构完全相同的子树

热度指数：1862 时间限制：C/C++ 3秒，其他语言6秒空间限制：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 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;
}

发表于 2021-07-24 14:53:30 回复(0)