判断两棵树是否相等

判断两棵树是否相等

两棵树是否相等的判断条件：
1. 树的结构一样
2. 对应节点存放的值相等

思路1：

首先对树的结果判断，若结构一样，则进行下一步节点中值的判断，若结构不一样，直接返回false==

1.定义一个flg来进行记录

boolean flg=false;

2.如果不存在节点（表示为空树），直接返回true

if(p==null && q==null){
return true;
}

3.如果节点存在，判断节点值是否一样

if(p!=null&&q!=null){
            if(p.val==q.val){
            
            }else {
             return false;
             }

4.若节点值一样，继续判断节点的左子树，右子树与另一棵树的左右子树是否相等（递归）
用flg来接受判断的结果

 if(p!=null&&q!=null){
 if(p.val==q.val){
 flg=isSameTree(p.left,q.left);
    if(flg==false){
        return false;
       }
  flg=isSameTree(p.right,q.right);
      if(flg==false){
         return false;
       }
   }
}

5.判断两棵树的结构是否一样

if(p==null&&q!=null||p!=null &&q==null){
            flg=false;
        }

6.最后返回flg的值

return flg;

完整代码如下：

public boolean isSameTree(TreeNode p, TreeNode q) {
        boolean flg=false;
        if(p==null && q==null){return true;}
        if(p!=null&&q!=null){
            if(p.val==q.val){
                flg=isSameTree(p.left,q.left);
                if(flg==false){
                    return false;
                }
                flg=isSameTree(p.right,q.right);
                if(flg==false){
                    return false;
                }
            }else {
                flg=false;
            }
        }
        if(p==null&&q!=null||p!=null &&q==null){
            flg=false;
        }
        return flg;
    }

思路2：

 public boolean isSameTree(TreeNode p, TreeNode q) {
        //1. 一个为空 一个不为空 【结构上】
        if( (p == null && q != null) || (p != null && q == null)) {
            return false;
        }
        //2. 此时 都不为空  或者 都为空 才能走到这里
        if(p == null && q == null ) {
            return true;
        }

        if(p.val != q.val) {
            return false;
        }
        //3. 此时代码走到这里  代表：p != null && q != null  && p.val == q.val
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }

原文地址：https://blog.csdn.net/2302_81707171/article/details/142737803

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！