首页 > 试题广场 >

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

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

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

给定彼此独立的两棵二叉树，树上的节点值两两不同，判断 t1 树是否有与 t2 树完全相同的子树。

子树指一棵树的某个节点的全部后继节点

数据范围：树的节点数满足 $0 < n \le 500000$ ，树上每个节点的值一定在32位整型范围内

进阶：空间复杂度: $O(1)$ ，时间复杂度 $O(n)$

示例1

输入

{1,2,3,4,5,6,7,#,8,9},{2,4,5,#,8,9}

输出

true

备注:

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Java

lgyt

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {

    //遍历主树
    //若数值相等，参试遍历同时遍历树进行判断
    TreeNode sub=null;
    public boolean check(TreeNode root1,TreeNode root2){
        if(root1==null&&root2==null){
            return true;
        }
        else if(root1==null||root2==null){
            return false;
        }
        else{
            if(root1.val!=root2.val){
                return false;
            }
            else{
                return check(root1.left,root2.left)&&check(root1.right,root2.right);
            }
        }       
    }
    public boolean preOrder(TreeNode root){
        if(root!=null){
            if(root.val==sub.val){
                if(check(root,sub)){
                    return true;
                }
                else return false;
            }
            return preOrder(root.left)||preOrder(root.right);
        }
        else return false;
    }
    public boolean isContains (TreeNode root1, TreeNode root2) {
        if(root2==null)return true;
        sub=root2;     
        //默认子树不空   
        return preOrder(root1);
    }
}

发表于 2024-07-27 15:46:58 回复(0)

Java

牛客839384289号

public boolean isContains (TreeNode root1, TreeNode root2) {
    // write code here
    if(root1==null && root2==null){
        return true;
    }
    if(root1==null||root2==null){
        return false;
    }
    if(root1.val==root2.val){
        return isSame(root1 ,root2);
    }
    return isContains(root1.left ,root2) || isContains(root1.right ,root2);
}

public boolean isSame(TreeNode root1 ,TreeNode root2){
    if(root1==null && root2==null){
        return true;
    }
    if(root1==null || root2==null){
        return false;
    }
    if(root1.val!=root2.val){
        return false;
    }
    return isSame(root1.left ,root2.left) && isSame(root1.right,root2.right);
}

编辑于 2024-03-10 16:39:40 回复(0)

Java

Yurino

先把t1和t2按照先序遍历序列化，验证是否为子串，用kmp算法

public class Solution {
    /**
     * 
     * @param root1 TreeNode类 
     * @param root2 TreeNode类 
     * @return bool布尔型
     */
    public boolean isContains (TreeNode root1, TreeNode root2) {
        // write code here
        String str1 = serialByPre(root1);
        String str2 = serialByPre(root2);
        return getIndexOf(str1,str2) != -1;
    }
    public String serialByPre(TreeNode head){
        if (head == null){
            return "#!";
        }
        String res = head.val + "!";
        res += serialByPre(head.left);
        res += serialByPre(head.right);
        return res;
    }
    //kmp
    public int getIndexOf(String s,String m){
        if (s == null || m == null || m.length() < 1 || s.length() < m.length()){
            return -1;
        }
        char[] sres = s.toCharArray();
        char[] mres = m.toCharArray();
        int si = 0;
        int mi = 0;
        int[] next = getNextArray(mres);
        while (si < sres.length && mi < mres.length ){
            if (sres[si] == mres[mi]){
                si++;
                mi++;
            }else if (next[mi] == -1){
                si ++;
            }else{
                mi = next[mi];
            }
        }
         return mi == mres.length ? si -mi :-1;
    }
    public int[] getNextArray(char[] ms){
        if (ms.length == 1){return new int[] {-1};}
        int[] next = new int[ms.length];
        next[0] = -1;
        next[1] = 0;
        int pos = 2;
        int cn = 0;
        while (pos < next.length){
            if (ms[pos - 1 ] == ms[cn]){
                next[pos ++] = ++cn;
            }else if (cn > 0){
                cn = next[cn];
            }else{
                next[pos++] = 0;
            }
        }
        return next;
    }
}

发表于 2021-08-12 22:00:55 回复(0)

Java

板爷

    //判断两棵树是否相同
    public boolean isTheSame (TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) {
            return true;
        }
        if ((root1 != null && root2 == null) || (root1 == null && root2 != null)) {
            return false;
        }
        if (root1.val != root2.val) {
            return false;
        }
        return isTheSame(root1.left, root2.left) && isTheSame(root1.right, root2.right);
    }
    
    public boolean isContains (TreeNode root1, TreeNode root2) {
        // write code here
        if (root1 == null) {
            return false;
        }
        //再添加一个递归结构，遍历找到合适的节点
        return isTheSame(root1, root2) || isContains(root1.right, root2) || isContains(root1.left, root2);
    }

发表于 2021-04-18 21:39:01 回复(0)

Java

花落梦里

    public boolean isContains (TreeNode root1, TreeNode root2) {
        //判断r1是否包含r2?
        if(root1==null) return false;
        if(root1.val!=root2.val)//两个根节点不想等，则用root1的左右子树分别和root2比较
            return isContains(root1.left,root2)||isContains(root1.right,root2);
        else//root1和root2相同，继续对比
            return isSame(root1,root2);
    }
    public boolean isSame(TreeNode root1,TreeNode root2){
        if(root1==null&&root2==null) return true;
        if(root1==null||root2==null) return false;
        //两个根节点都不为空，继续比较
        return (root1.val==root2.val)&&isSame(root1.left,root2.left)&&isSame(root1.right,root2.right);
    }

发表于 2021-03-27 09:33:46 回复(2)

Java

牛客915296776号

public class Solution {
    public boolean isContains (TreeNode root1, TreeNode root2) {
        if (root1 == null) return false;
        return isEquals(root1, root2) || isContains(root1.left, root2) || isContains(root1.right, root2);
    }
    
    private boolean isEquals(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) return true;
        if (root1 == null || root2 == null) return false;
        if (root1.val != root2.val) return false;
        return isEquals(root1.left, root2.left) && isEquals(root1.right, root2.right);
    }
}

发表于 2020-12-21 13:28:48 回复(0)

Java

六娃lw

LeetCode上的题目有一点差别，就是判断是否是相同拓扑结构时，null与非null匹配返回true，而此题null必须与null配对。

public class Solution {
    /**
     * 
     * @param root1 TreeNode类 
     * @param root2 TreeNode类 
     * @return bool布尔型
     */
    public boolean isContains (TreeNode root1, TreeNode root2) {
        // write code here
        if(root1 == null && root2 == null){return true;}
        if(root1 == null){return false;}
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offerLast(root1);
        while(!queue.isEmpty()){
            int len = queue.size();
            for(int i = 0; i < len; ++i){
                TreeNode root = queue.pollFirst();
                if(helper(root, root2)){
                    return true;
                }else{
                    if(root.left != null){queue.offerLast(root.left);}
                    if(root.right != null){queue.offerLast(root.right);}
                }
            }
        }
        return false;
    }
    
    public boolean helper(TreeNode root1, TreeNode root2){
        if(root1 != null && root2 != null){
            return root1.val == root2.val && 
                helper(root1.left, root2.left) && 
                helper(root1.right, root2.right);
        }else if(root1 == null && root2 == null){
            return true;
        }
        return false;
    }
}

编辑于 2020-12-15 15:14:09 回复(0)

Java

fsSpdTas

终于自己搞出来了

public boolean isContains (TreeNode root1, TreeNode root2) {
boolean left;
boolean right;
if(root1!=null&&root2!=null){
if(root1.val==root2.val){
left=isContains(root1.left,root2.left);
right=isContains(root1.right,root2.right);
return left&&right;
}else{
left=isContains(root1.left,root2);
right=isContains(root1.right,root2);
return left||right;
}
}
if(root1==null&&root2==null)return true;
return false;
}
}

发表于 2020-11-13 23:37:11 回复(0)

Java

matrixZ

中序遍历root1和root2，获得字符串，判断root2是否为root1的子串

import java.util.*;

public class Solution {

    public boolean isContains (TreeNode root1, TreeNode root2) {
        // write code here
        StringBuilder builder1 = new StringBuilder();
        StringBuilder builder2 = new StringBuilder();
        preOrder(root1,builder1);
        preOrder(root2,builder2);
        if(builder1.toString().contains(builder2.toString())){
            return true;
        }else {
            return false;
        }
    }
    
    //中序遍历并填充stringbuilder
    static void preOrder(TreeNode treeNode,StringBuilder stringBuilder){
        if(treeNode==null){
            return;
        }
        preOrder(treeNode.left,stringBuilder);
        stringBuilder.append(treeNode.val);
        preOrder(treeNode.right,stringBuilder);
    }
}

编辑于 2020-09-15 20:47:30 回复(5)