首页 > 试题广场 >

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

[编程题]判断t1树中是否有与t2树拓扑结构完全相同的子树
  • 热度指数:1839 时间限制: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

输入

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

备注:

先层次遍历给两树上所有节点编号,然后比较两棵树的先序和中序序列是否都相等
发表于 2019-12-07 22:21:18 回复(0)
这个题目非常经典,有如下三个可能性:
  1. A和B两棵树完全一样;
  2. B树为A树的左子树;
  3. B树为A树的右子树。
然后递归求解,挨个检查两棵树的节点值是否相等。(1) 如果B树没有结点了,说明所有节点都检查完了还没发现不相等的情况,找到了B树在A树中的子结构;(2) 如果A树没有节点了,说明A树剩下的子树部分规模比B树小,不可能再存在B树的结构;(3) A树和B树的节点值不相等也说明结构不符合。
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;
    }
}

发表于 2021-12-04 09:32:12 回复(0)
#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;

}
发表于 2020-02-06 10:50:42 回复(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;
}

编辑于 2022-11-15 12:46:57 回复(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;
}

发表于 2021-07-24 14:53:30 回复(0)
直接使用String记录下n树的所有字符串输入,和m树的所有字符串输入。因为输入必须要符合树的定义,并且可以由输入确定出唯一的一棵树,因此使用该方法可以直接取巧的根据比较两个字符串之间存在互相包含关系而确定两棵树是否存在包含关系。核心代码如下:
        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));



发表于 2020-08-09 16:34:29 回复(0)