首页 > 试题广场 >

判断二叉树是否相等

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

热度指数：24200 时间限制：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，点此查看相关信息

算法知识视频讲解

Java

liabi4hao

public boolean isSameTree (TreeNode p, TreeNode q) {
// write code here
if(p == null && q == null){
return true;
}
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);
}

发表于 2022-03-09 00:27:15 回复(0)

Java

菲尼克斯弗兰克

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

发表于 2021-10-20 10:07:50 回复(0)

Java

威廉古堡的秘密

    public boolean isSameTree (TreeNode p, TreeNode q) {
        // write code here
        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);
    }

主要通过递归来实现，比较二叉树的值以及其左节点和右节点是否i相等

注意前置条件的判断处理

发表于 2021-05-11 15:27:00 回复(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)

Java

就是很菜

java版本的非递归实现

import java.util.*;
import Offer3.Solution20.TreeNode;
public class Solution22 {

	  public boolean isSameTree(TreeNode p, TreeNode q) {
		  if(p==null&&q==null)
			  return true;
		  if(p==null||q==null)
			  return false;
		  Queue<TreeNode> queue1 = new LinkedList<>();
		  Queue<TreeNode> queue2 = new LinkedList<>();
		  queue1.offer(p);
		  queue2.offer(q);
		  while(!queue1.isEmpty()&&!queue2.isEmpty()) {
			  TreeNode node1 = queue1.poll();
			  TreeNode node2 = queue2.poll();
			  if(node1==null&&node2==null)
				  continue;
			  if(node1==null||node2==null)
				  return false;
			  if(node1.val!=node2.val)
				  return false;
				  queue1.offer(node1.left);
				  queue1.offer(node1.right);
                  queue2.offer(node2.left);
				  queue2.offer(node2.right);

		  }
		  if(!queue1.isEmpty()||!queue2.isEmpty()) {
			  return false;
		  }
		  return true;
	  }

}

发表于 2020-04-12 15:51:21 回复(0)

Java

key、L

很简单的递归哇

public class Solution {
    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 == null && q != null)
            return false;
        else
            return (p.val == q.val)&&isSameTree(p.left, q.left)
            &&isSameTree(p.right, q.right);
    }
}

发表于 2020-01-13 20:30:26 回复(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)

Java

回去等通知吧

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

发表于 2018-07-18 10:57:34 回复(0)

Java

jRomann

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 isSameTree(p.left,q.left) &&isSameTree(p.right,q.right);
return false;
}
}

发表于 2018-06-20 11:00:44 回复(0)

Java

叶青云


	
	
		public class Solution {
	

	
		    public boolean isSameTree(TreeNode p, TreeNode q) {
	

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

	
		            returnp == null&& q == null;         
	

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

	
		    }
	

	
		}

编辑于 2018-04-03 17:36:26 回复(0)

Java

七仔0312

递归

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);
    }
}

发表于 2018-03-16 17:21:59 回复(0)

Java

安徒生的谎言

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSameTree(TreeNode tree1, TreeNode tree2) {
        boolean result=true;
        if(tree1==null&&tree2==null) {
            return true;
        }
        if((tree1!=null&&tree2==null)||(tree1==null&&tree2!=null)) {
            return false;
        }
        if(tree1.val!=tree2.val){
            return false;
        }
        boolean left=isSameTree(tree1.left, tree2.left);
        boolean right=isSameTree(tree1.right, tree2.right);
        if(left==true&&right==true) {
            result=true;
        }else
            result=false;
        return result;
    }
}

发表于 2018-03-06 11:06:27 回复(0)

Java

无名huster

public class Solution {
    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 != null && q == null){
            return false;
        }
        if(p.val == q.val){
            return checkTree(p,q);
        }
        return false;
    }
    
    private boolean checkTree(TreeNode node1 , TreeNode node2){
        if(node1 == null && node2 == null ){
            return true;
        }
        if(node1 == null && node2 != null ){
            return false;
        }
        if(node1 != null && node2 == null){
            return false;
        }
        if(node1.val != node2.val){
            return false;
        }else{
            return checkTree(node1.left,node2.left)&&checkTree(node1.right,node2.right);
        }
    }
}

发表于 2017-09-05 13:37:14 回复(0)

Java

葵司

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null && q==null){
            return true;
        }
		if(p==null&&q!=null || q==null&&p!=null){
            return false;
        }
        if(p!=null && q!=null){
            return (p.val==q.val)&&(isSameTree(p.left, q.left))&&(isSameTree(p.right, q.right));
        }
        return false;
    }
}

发表于 2017-09-01 14:31:42 回复(0)

Java

卖萌の哈士奇

    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 isSameTree(q.left,p.left) && isSameTree(p.right,q.right) && p.val == q.val;
    }

发表于 2017-08-22 10:08:54 回复(0)

Java

萨仁朝格图（大家去脉脉沟通）

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 isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
        return false;
    }
}

发表于 2017-08-16 18:25:56 回复(0)

Java

pp11

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        return isSameTree2(p, q);
    }
    public boolean isSameTree2(TreeNode tree1, TreeNode tree2) {
        if (tree1 == null && tree2 == null)
            return true;
        if (tree1 == null || tree2 == null)
            return false;
        if (tree1.val != tree2.val)
            return false;
        return isSameTree2(tree1.left, tree2.left) && isSameTree2(tree1.right, tree2.right);
    }
}

发表于 2017-08-09 15:49:39 回复(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

948937912

public boolean isSameTree(TreeNode p, TreeNode q) {

boolean flag = false;

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

if (p != null && q != null && p.val == q.val){

try {

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

}catch (Exception e){

}

return flag;

}

return flag;

}

发表于 2017-06-05 20:07:25 回复(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);
}