首页 > 试题广场 >

判断二叉树是否相等

[编程题]判断二叉树是否相等

热度指数：24397 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给出两个二叉树，请写出一个判断两个二叉树是否相等的函数。

判断两个二叉树相等的条件是：两个二叉树的结构相同，并且相同的节点上具有相同的值。

数据范围：树上的节点数满足 $0 \le n \le 200$ ，树上节点的值满足 $0 \le val \le 5000$
进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

示例1

输入

{1},{1}

输出

true

示例2

输入

{1,2},{1,#,2}

输出

false

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

算法知识视频讲解

JacobGo！

/*
	 * 简单的递归实现
	 */
	public boolean isSameTree(TreeNode p, TreeNode q) {
		if (p == null && q == null)
			return true;
		if (p == null || q == null)
			return false;
		if (p.val == q.val) {
			return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
		}
		return false;
	}

发表于 2017-08-05 11:08:46 回复(0)

C/C++

J.Fan

//非递归实现，主要思路是用两个队列进行层次遍历
class Solution {
public:
    bool isSameTree(TreeNode *p, TreeNode *q) {
        if(p==NULL && q==NULL)
            return true;
        queue<TreeNode*> q1,q2;
        q1.push(p);q2.push(q);
        TreeNode *tmp1,*tmp2;
        while(!q1.empty()&&!q2.empty())
        {
            tmp1 = q1.front();
            tmp2 = q2.front();
            q1.pop();q2.pop();
            if(tmp1==NULL && tmp2==NULL)
                continue;
            if(tmp1==NULL || tmp2==NULL)
                return false;
            if(tmp1->val!=tmp2->val)
                return false;
            if(tmp1!=NULL)
            {
                q1.push(tmp1->left);
                q1.push(tmp1->right);
            }
            if(tmp2!=NULL)
            {
                q2.push(tmp2->left);
                q2.push(tmp2->right);
            }
        }
        if(!q1.empty()||!q2.empty())
            return false;
        return true;
    }
};

发表于 2018-09-28 11:46:42 回复(1)

Java

ephonzhang

public class Solution {

public boolean isSameTree(TreeNode p, TreeNode q) {

if (p == null || q == null) return p == q;

return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);

}

发表于 2017-04-23 23:00:32 回复(0)

Java

tornado123

    /**
     * 
     * @param p TreeNode类 
     * @param q TreeNode类 
     * @return bool布尔型
     */
    public boolean isSameTree (TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }else if (p == null || q == null) {
            return false;
        }else if (p.val != q.val) {
            return false;
        }
        // 两个数均不为null, 且 val值相等，直接递归比较下一层
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

发表于 2020-10-14 10:02:30 回复(0)

LiberHome

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null){
            return true;
        }
        if((p == null && q != null)||(p != null && q == null)){
            return false;
        }
        //不要忘记判断节点的值哦~
        if(p.val !=q.val){
            return false;
        }
        return  isSameTree(p.right,q.right) && isSameTree(p.left, q.left) ;
    }
}

发表于 2020-07-10 13:55:41 回复(0)

ExtraLocker

class Solution {
public:
    bool isSameTree(TreeNode *p, TreeNode *q) {
        if (p == nullptr || q == nullptr) return p == q;
        return p -> val == q -> val && isSameTree(p -> left, q -> left) && isSameTree(p -> right, q -> right);
    }
};

发表于 2020-03-31 18:56:28 回复(0)

望月草

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

发表于 2019-08-15 23:07:48 回复(0)

tuweilong

/*
递归求解。
当前节点相等，左子树，右子树也相等，则认为这两个树是相等的。
*/
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;
        if (p.val != q.val) return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

发表于 2019-06-19 20:21:24 回复(0)

HW柯可

//递归，真香！
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q==null)
            return true;
        if(p==null||q==null)
            return false;
        return p.val==q.val&&isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
}

编辑于 2018-09-23 10:45:00 回复(0)

小Andy

class Solution {

public:

bool isSameTree(TreeNode *p, TreeNode *q) {

if(p==NULL && q==NULL)

return true;

else if(p==NULL || q==NULL) //结构不同

return false;

else if(p->val != q->val)

return false;

else

return (isSameTree(p->left,q->left) && isSameTree(p->right,q->right));

}

};

发表于 2017-10-10 09:02:31 回复(0)

C/C++

nbgao

class Solution {
public:
    bool isSameTree(TreeNode *p, TreeNode *q) {
        if(p == NULL && q == NULL)
        	return true;
        else if(p == NULL || q == NULL)
        	return false;
        else if(p->val == q->val)
        	return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
		return false;
    }
};

发表于 2017-08-04 01:12:12 回复(0)

Java

Zfirsty

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

发表于 2017-07-27 15:40:24 回复(0)

Java

二面挂王

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

发表于 2017-06-05 09:42:54 回复(0)

haha_ha

class Solution {

public:

bool isSameTree(TreeNode *p, TreeNode *q) {

if(p==NULL&&q==NULL)

return true;

else if (p!=NULL&&q!=NULL)

return checkSame(p,q);

else

return false;

}

bool checkSame(TreeNode *p, TreeNode *q){

if(p==NULL&&q==NULL)

return true;

if((p!=NULL&&q==NULL)||(p==NULL&&q!=NULL))

return false;

if(p->val!=q->val)

return false;

return checkSame(p->left, q->left)&&checkSame(p->right, q->right);

}

};

发表于 2017-05-06 11:04:37 回复(0)

Java

丫丁

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

编辑于 2017-05-02 19:16:41 回复(0)

冷色探戈

/**
* 两棵树是否是同一棵树
* 递归解法
* @param p
* @param q
* @return
*/
public boolean isSameTree_2(TreeNode p, TreeNode q) {
  if (p == null && q == null) {
      return true;
  }
  if (p == null || q == null) {
      return false;
  }
  if (p.val != q.val) {
      return false;
  }
  return isSameTree_2(p.left, q.left) && isSameTree_2(p.right, q.right);
}

编辑于 2017-03-29 23:13:23 回复(0)

Java

詆調壹點

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

编辑于 2016-11-01 21:34:43 回复(0)

缘故

  classSolution { 
  public: 
      bool isSameTree(TreeNode
  *p, TreeNode *q) { 
          returnf(p,q); 
      } 
      bool f(TreeNode*a,TreeNode
  *b){ 

          if(a==NULL&&b==NULL)returntrue; 

          if(a==NULL&&b!=NULL)returnfalse; 

          if(a!=NULL&&b==NULL)returnfalse; 

          if(a->val!=b->val)returnfalse; 

              returnf(a->left,b->left)&&f(a->right,b->right); 
            
      } 
  }; 

发表于 2015-08-31 20:08:15 回复(0)

Java

放学后我不走~

1. 是否都为空，是则返回true

否则：即有非空的，则2

2. 是非有非空，是则返回false

否则：即都不为空，则3

3. 值是否相等 && 左子数是否相等 && 右子数是否相等

代码如下：

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

编辑于 2018-08-31 10:59:59 回复(0)

xxj

class Solution {
public:
bool isSameTree(TreeNode *p, TreeNode *q) {
if(p==NULL && q==NULL) return true;
else if(p==NULL || q==NULL) return false;
else if(p->val != q->val)return false;

return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}
};

发表于 2014-11-14 11:01:22 回复(4)