算法工程题（二叉树递归）

*  题意说明：
*      给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
*      如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
*
* 示例 1：
*  输入：p = [1,2,3], q = [1,2,3]
*  输出：true
*
* 示例 2：
*  输入：p = [1,2], q = [1,null,2]
*  输出：false
*
* 示例 3：
*  输入：p = [1,2,1], q = [1,1,2]
*  输出：false
*
* 提示：
*  两棵树上的节点数目都在范围 [0, 100] 内
*  -104 <= Node.val <= 104
*
* Related Topics
*  树
*  深度优先搜索
*  广度优先搜索
*  二叉树
*
* @Date 2023/9/4 9:36
* @Version 1.0

示例：

public class IsSameTree_019 {
 
    public static void main(String[] args) {
        // 测试验证
    }
 
    public static boolean isSameTree(TreeNode p, TreeNode q) {
        return false;
    }
}

使用递归的方式来实现：

public class IsSameTree_019 {
 
  public static void main(String[] args) {
    TreeNode p;
    p = new TreeNode(1);
    p.left = new TreeNode(2);
    p.right = new TreeNode(3);
    TreeNode q;
    q = new TreeNode(1);
    q.left = new TreeNode(2);
    q.right = new TreeNode(3);
    // 测试验证
    System.out.println(isSameTree(p,q));
  }
 
  public static boolean isSameTree(TreeNode p, TreeNode q){
    //首先判断是否俩个节点为空
    if(p == null && q == null)
      return true;
    //判断俩边节点是否对等 返回为false
    if((q == null && p != null) || (p == null && q != null))
      return false;
    //判断值不相同也返回false
    if (p.val != q.val){
      return false;
    }else
      return (isSameTree(p.left,q.left) && isSameTree(p.right,q.right));
  }
 
  static class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
 
    TreeNode() {
    }
 
    TreeNode(int val) {
      this.val = val;
    }
 
    TreeNode(int val, TreeNode left, TreeNode right) {
      this.val = val;
      this.left = left;
      this.right = right;
    }
  }
}