给定两个树,如果它们在结构上相同,则返回True,它们由以相同方式排列相同值的节点组成

xbp102n0  于 2022-10-15  发布在  Eclipse
关注(0)|答案(7)|浏览(138)
public static boolean identical(treenode<Integer> root1,treenode<Integer> root2)
    {
        boolean ans;
        for(int i=0;i<root1.children.size();i++)
        for(int j=0;j<root2.children.size();j++)
        {
         boolean subans=identical(root1.children.get(i),root2.children.get(j));
         ans=subans;
        }
        if(root1.data==root2.data)
        {
            ans=true;
        }/* what's wrong with the code*/
        else{
            ans=false;
        }
        return ans;
    }/* how can i improve it ? */

我不能理解为什么我的代码不工作。请告诉我修复它的解决方案。

rslzwgfq

rslzwgfq1#

在计算这些递归调用的布尔返回之前,您的for循环将遍历identical的每个递归调用。换句话说,您并没有通过递归调用计算所有子级的数据。对于您的代码,我相信您可能只计算树中每个节点的最后一个子节点(沿着最右边)。
您还有一个嵌套的for循环,这在本例中是不必要的。
我的建议是:
1)检查当前节点的值是否相同。如果不是,或者如果至少有一个为空,则立即返回FALSE。
2)检查两个节点的子节点大小是否相同。如果不是,则返回False。
3)对每个子节点进行递归调用。
这是一次深度优先、左侧优先的搜索。

tvz2xvvm

tvz2xvvm2#

private boolean structurallyIdentical(Node tnode, Node onode) {
    if(tnode == null && onode == null) {
        return true;
    }
    if(tnode != null && onode != null) {
        // check that the left branch is identical
        boolean left = structurallyIdentical(tnode.left, onode.left);
        // check that the right branch is identical
        boolean right = structurallyIdentical(tnode.right, onode.right);
        // only identical, if both branches match
        return (left && right);
    }
    return false;
}
wr98u20j

wr98u20j3#

在@Vansh Nandwani回答的基础上做了一些改进。SBT=相同的二叉树

public  boolean SBT(BinNode root1, BinNode root2)
    {
        if (root1 == null && root2 == null) return true;
        if (root1 != null && root1 != null) {
            if (root1.value() == root2.value())//check if the values are the same 
               {
                boolean left = SBT(root1.left(), root2.left());
                boolean right = SBT(root1.right(), root2.right);
                return (left && right);}
                } 
        return false;
    }
uubf1zoe

uubf1zoe4#

public class Solution {

/*  TreeNode structure 
    class TreeNode<T> {
        T data;
        ArrayList<TreeNode<T>> children;

        TreeNode(T data){
            this.data = data;
            children = new ArrayList<TreeNode<T>>();
        }
    }*/

    public static boolean checkIdentical(TreeNode<Integer> root1, TreeNode<Integer> root2){

        if(root1.children.size()!=root2.children.size())
        {
            return false;
        }
         if(root1.children.size()==root2.children.size()){
            if(root1.data==root2.data)
            {
                for(int i=0 ,j=0;i<root1.children.size()&&j<root2.children.size();i++ ,j++){
                    checkIdentical(root1.children.get(i),root2.children.get(j));
                        return true;
                }
            }
        }
        return false;
    }
}
9bfwbjaz

9bfwbjaz5#

bool areIdentical(TreeNode<int> *root1, TreeNode<int> * root2) 
    {bool ans=false;

        if(root1->children.size()!=root2->children.size())
        {
            ans =false;
        }
         if(root1->children.size()==root2->children.size()){
            if(root1->data==root2->data)
            {
                for(int j=0;j<root1->children.size();j++){
                    areIdentical(root1->children[j],root2->children[j]);
                    ans=true;
                }
            }
        }
        return ans;
    }
6kkfgxo0

6kkfgxo06#

对于一般树
方法一:

bool areIdentical(TreeNode<int> *root1, TreeNode<int> * root2) {

    if(root1 == NULL && root2 == NULL){
        return true;
    }
    if((root1 == NULL && root2 != NULL) || (root1 != NULL && root2 == NULL)){
        return false;
    }
    if((root1->data != root2->data)|| (root1->children.size() != root2->children.size())){
         return false;
    }
    else if(root1->children.size() == root2->children.size()){
        if(root1->data == root2->data){
           for(int i=0,j=0;i<root1->children.size()&&j<root2->children.size();i++,j++){
                    areIdentical(root1->children[i],root2->children[j]);
                    return true;
           }
        }
    }
    return false;

}

//此解决方案可能无法通过某些测试用例,但方法2:完全正常工作
方法二:

bool areIdentical(TreeNode<int> *root1, TreeNode<int> * root2) {
    if(root1 == NULL && root2 == NULL){
        return true;
    }
    if((root1 == NULL && root2 != NULL) || (root1 != NULL && root2 == NULL)){
        return false;
    }
    if((root1->data != root2->data)|| (root1->children.size() != root2->children.size())){
         return false;
    }
    for(int  i = 0;i < root1->children.size();++i){
        TreeNode<int>* child1 = root1->children[i];
        TreeNode<int>* child2 = root2->children[i];
        if(!areIdentical(child1,child2)){
            return false;
        }
    }
    return true;

}
gzjq41n4

gzjq41n47#

结构相同

public static boolean checkIdentical(TreeNode<Integer> root1, TreeNode<Integer> root2){

    int size1=root1.children.size();
    int size2=root2.children.size();
    if(root1==null && root2==null){
        return true;
    }
    if((root1==null && root2!=null) || (root1!=null && root2==null)){
        return false;
    }
    if((root1.data!=root2.data)||(size1!=size2)){
        return false;
    }

    if(size1==size2){
        if(root1.data==root2.data){
            for(int i =0;i<size1;i++){
             for(int j=0;j<size2;j++){
                 TreeNode<Integer> child1=root1.children.get(i);
                 TreeNode<Integer> child2=root2.children.get(i);
                 if(!checkIdentical(child1,child2)){
                     return false;
                 }
             }   
            }
        }
    }
    return true;

}

相关问题