首页 > 试题广场 >

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

[编程题]判断t1树中是否有与t2树完全相同的子树
  • 热度指数:18828 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定彼此独立的两棵二叉树,树上的节点值两两不同,判断 t1 树是否有与 t2 树完全相同的子树。

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

数据范围:树的节点数满足 ,树上每个节点的值一定在32位整型范围内
进阶:空间复杂度: ,时间复杂度
示例1

输入

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

输出

true

备注:

说明:本题目包含复杂数据结构TreeNode,点此查看相关信息
    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)
中序遍历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)
#include <stdbool.h>

typedef struct TreeNode* NodePtr;

// function prototype
bool isSameTree(const NodePtr root1, const NodePtr root2);

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 
 * @param root1 TreeNode类 
 * @param root2 TreeNode类 
 * @return bool布尔型
 */
bool isContains(const NodePtr root1, const NodePtr root2) {
  // 算法框架,逻辑上要找到通路!
  if (!root1) return false;
  return isSameTree(root1, root2)
      || isContains(root1->left, root2) 
      || isContains(root1->right, root2);
}

bool isSameTree(const NodePtr root1, const NodePtr root2) {
  if (!root1 || !root2) return root1 == root2;
  return root1->val == root2->val
      && isSameTree(root1->left, root2->left)
      && isSameTree(root1->right, root2->right);
}

发表于 2021-07-07 09:32:13 回复(0)
//树的子结构



 public boolean isContains (TreeNode root1, TreeNode root2) {
       if(root1==null&&root2==null) return true;
       if(root1==null||root2==null) return false;
       return recur(root1,root2)||isContains(root1.left,root2)||isContains(root1.right,root2);   
    }
    
    public boolean recur(TreeNode A,TreeNode B){
        if(B==null) return true;
        if(A==null) return false;
        return B.val==A.val&&recur(A.left,B.left)&&recur(A.right,B.right);
    }
发表于 2020-08-28 14:56:41 回复(1)
    //一种清晰些的写法,isEqual + isContains 看的人云里雾里
    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 isContains(root1.left, root2.left) && isContains(root1.right, root2.right);
        }
    
        return isContains(root1.left, root2) || isContains(root1.right, root2);
    }


发表于 2024-03-16 17:47:26 回复(0)
终于自己搞出来了
    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)
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)
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param root1 TreeNode类 
     * @param root2 TreeNode类 
     * @return bool布尔型
     */
    bool isContains(TreeNode* root1, TreeNode* root2) {
        // write code here
        if (root1 == nullptr) return false;
        if (dfs(root1, root2)) return true;
        return isContains(root1->left, root2) || isContains(root1->right, root2);
    }

    bool dfs(TreeNode* root1, TreeNode* root2) {
        if (root1 == nullptr && root2 == nullptr) return true;
        else if (root1 != nullptr && root2 == nullptr) return false;
        else if (root1 == nullptr && root2 != nullptr) return false;
        if (root1->val != root2->val) return false;
        return dfs(root1->left, root2->left) && dfs(root1->right, root2->right);
    }
};

发表于 2023-09-09 17:12:29 回复(0)
class Solution:
    def isContains(self , root1: TreeNode, root2: TreeNode) -> bool:
        # write code here        
        def isSameTree(root1, root2):
            # 检查两个数是否相同
            if root1 is None and root2 is None:
                return True 
            if root1 is None or root2 is None or root1.val != root2.val:
                return False 
            return isSameTree(root1.left, root2.left) and isSameTree(root1.right, root2.right)

        # 基础情况:
        # 1)两个都是空
        if root1 is None and root2 is None:
            return True 
        # 2)root1为空,root2非空,返回否
        if root1 is None and root2 is not None:
            return False 
        # 3)root1和root2是相同的树
        if isSameTree(root1, root2):
            return True 
        return self.isContains(root1.left, root2) or self.isContains(root1.right, root2)
发表于 2023-04-26 09:48:51 回复(0)
package main
import . "nc_tools"
/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 
 * @param root1 TreeNode类 
 * @param root2 TreeNode类 
 * @return bool布尔型
*/
func isContains( root1 *TreeNode ,  root2 *TreeNode ) bool {
    if root1==nil&&root2==nil{
        return true
    }else if root1==nil||root2==nil{
        return false
    }else if root1.Val==root2.Val{
        return check(root1,root2)
    }else{
        return isContains(root1.Left,root2)||isContains(root1.Right,root2)
    }
}

func check(r1,r2 *TreeNode)bool{
    if r1==nil&&r2==nil{
        return true
    }else if r1==nil||r2==nil||r1.Val!=r2.Val{
        return false
    }else{
        return check(r1.Left,r2.Left)&&check(r1.Right,r2.Right)
    }
}

发表于 2023-01-31 21:51:06 回复(0)
/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 * };
 */

/**
 *
 * @param root1 TreeNode类
 * @param root2 TreeNode类
 * @return bool布尔型
 */
 //先找到root2的根在root1中的位置 提取root1中以root2的根为根的子树
 //再判断两个子数是否完全相同
bool preorder(struct TreeNode* root1, struct TreeNode* root2) {
    //static int count = 0;
    if (NULL != root1 && NULL != root2) {
        if (root1->val != root2->val)
            return false;
        return preorder(root1->left, root2->left) &&
               preorder(root1->right, root2->right) ;
        // preorder(root1->left, root2->left);
        // preorder(root1->right, root2->right);
    }
    if (NULL != root1 && NULL == root2)
        return false;
    if (NULL == root1 && NULL != root2)
        return false;
    return true;
}
struct TreeNode* post(struct TreeNode* root,int value) {
    //二叉树查找某个点
    if(NULL==root)
       return NULL;
    struct TreeNode* temp=NULL;
    if(root->left!=NULL){
        temp=post(root->left,value);
        if(temp!=NULL)
           return temp;
    }
    if(root->right!=NULL){
        temp=post(root->right,value);
        if(temp!=NULL)
           return temp;
    }
    
    if(root->val==value)
            return root;
        // post(root->left,value);
        // post(root->right,value);
        //arr[count++] = root->val;
    
    return temp;

}
bool isContains(struct TreeNode* root1, struct TreeNode* root2 ) {
    // write code here
    struct TreeNode* temp=post(root1,root2->val);
    if(temp==NULL){
        return false;
    }
    return preorder(temp,root2);

}

发表于 2023-01-10 20:13:09 回复(0)
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     *
     * @param root1 TreeNode类
     * @param root2 TreeNode类
     * @return bool布尔型
     */
    TreeNode root;

    public boolean isContains(TreeNode root1, TreeNode root2) {
        // write code here
        if (root2 == null) {
            return true;
        }
        middle(root1, root2);
        if (root == null) {
            return false;
        } else {
            return isEqual(root, root2);
        }


    }


    private boolean isEqual(TreeNode root1, TreeNode root2) {
        return middleValue(root1, root2);
    }

	private boolean middleValue(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 middleValue(root1.left, root2.left) && middleValue(root1.right, root2.right);
	}


    private void middle(TreeNode root1, TreeNode root2) {
        if (root1.val == root2.val) {
            root = root1;
        }
        if (root1.left != null) {
            middle(root1.left, root2);
        }

        if (root1.right != null) {
            middle(root1.right, root2);

        }
    }

}

发表于 2022-10-08 14:34:24 回复(0)
使用后序遍历即可完成正确的比较,因为子树的root在最后,确保了子树的全部元素均在此之前。
class Solution:
    def postorder(self, root, res):
        if not root:
            return
        self.postorder(root.left, res)
        self.postorder(root.right, res)
        res.append(root.val)
        return

    def isContains(self , root1 , root2 ):
        res_1 = []
        res_2 = []
        self.postorder(root1, res_1)
        self.postorder(root2, res_2)
        print(res_1)
        print(res_2)
        for i in range(len(res_1)):
            if res_1[i] == res_2[0]:
                break
        for j in range(len(res_2)):
            if res_1[i] != res_2[j]:
                return False
            i += 1
        return True
发表于 2022-09-18 09:41:56 回复(0)
class Solution:
    def isContains(self , root1: TreeNode, root2: TreeNode) -> bool:

        def dfs_same(t1, t2):
            if not t1 and not t2: return True
            if not t1 or not t2: return False
            l, r = dfs_same(t1.left, t2.left), dfs_same(t1.right, t2.right)
            return l and r and t1.val == t2.val

        def dfs(x):
            if not x: return not root2
            return dfs_same(x, root2) or dfs(x.left) or dfs(x.right)

        return dfs(root1)
发表于 2022-03-14 16:08:58 回复(0)
class Solution:
    def isContains(self , t1: TreeNode, t2: TreeNode) -> bool:
        # write code here
        if not t1 and t2:
            return False
        if not t2 and t1:
            return False
        if not t2 and not t1:
            return True
        if t1.val==t2.val:
            return self.isContains(t1.left, t2.left) and self.isContains(t1.right, t2.right)
        else:
            return self.isContains(t1.left, t2)&nbs***bsp;self.isContains(t1.right, t2)

发表于 2022-01-11 06:48:18 回复(0)
按官方题解,中序遍历+ 查找子串,有个用例不通过,不知道有没有人遇到相似问题,C++版本
发表于 2021-12-29 16:55:49 回复(2)
class Solution:
    def isContains(self , root1: TreeNode, root2: TreeNode) -> bool:
        def recur(root):
            if not root: return "#"
            return '*'+str(root.val)+recur(root.left)+recur(root.right)
        return recur(root2) in recur(root1)

发表于 2021-11-21 20:16:13 回复(0)
class Solution:
    def isContains(self , root1 , root2 ):
        # write code here
        if not root1:
            return False
        if not root2:
            return True
        self.res = False
        def dfs(root1, root2):
            if not root1:
                return
            if root1.val == root2.val:
                if self.process(root1, root2):
                    self.res = True
                    return 
            dfs(root1.left, root2)
            dfs(root1.right, root2)
        dfs(root1, root2)
        return self.res
    
    
    def process(self, root1, root2):
        if root1 == None and root2 == None:
            return True
        if root1 == None and root2 != None:
            return False
        if root1 != None and root2 == None:
            return False
        if root1.val == root2.val:
            return self.process(root1.left, root2.left) and self.process(root1.right, root2.right)
        else:
            return False

发表于 2021-09-06 20:21:12 回复(0)
先把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)
class Solution {
public:
    bool isContains(TreeNode* root1, TreeNode* root2) {
        if(root1==nullptr) return false;
        return isSame(root1,root2)
            || isContains(root1->right,root2)
            || isContains(root1->left,root2);
    }
    bool isSame(TreeNode * x,TreeNode *y){
        if(x!=nullptr&&y==nullptr ||x==nullptr&&y!=nullptr) return false;
        if(x==nullptr &&y==nullptr) return true;
        return x->val==y->val
            && isSame(x->right,y->right)
            && isSame(x->left,y->left);
    }
};

发表于 2021-07-14 14:17:03 回复(0)