题目内容

给你两棵二叉树的根节点 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

提示

1、两棵树上的节点数目都在范围 [0, 100] 内
2、-10^4 <= Node.val <= 10^4

题解

本题直接按照定义求解，即直接遍历两棵树，如果对应节点不一样，就不是相同的树，如果全部遍历完，都一致，则一定是相同的树，具体看代码就好了。这里给出递归的最简单的写法。

代码

/**
 * Definition for a binary tree node.
 * public 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;
 *     }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(!q&&!p) return true;//是两颗空树，也是一样的树，返回true
      	if(!p || !q || p->val !=q->val) return false;//当存在对应节点的值不同或者两棵树一个空一个不空的情况，返回false
      	return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);//递归求解左右子树
    }
}