题目描述

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例1：
No.100 相同的树 (Easy) - 图1
返回true

示例2：
No.100 相同的树 (Easy) - 图2
返回false

思路

仍然是树的遍历，如果两个树相同，那么对其进行前序或者中序或者后序遍历，得到的结果必然是一样的 （注意，反过来不成立，即如果前序遍历相同，并不能还原成两棵相同的树）。在此只需要对两棵树进行前序遍历，挨个比较结点的值即可。比较共如下几种情况：

  1. 两个结点都为null -> 返回true
  2. 一个结点为null, 一个结点不为null -> 返回false
  3. 都不为null, 但结点值不同 -> 返回false

有的同学会有疑惑，为什么没有第4种情况，即:

  1. 都不为null, 结点相同 -> 返回true

因为当两棵树的某一个结点的值相同时，并不代表这两棵树完全相同，例如示例2中，根结点相同并不意味着两棵树相同。

那么条件3为什么成立呢？为什么不相同的时候直接返回false
因为只要有一个结点不同，那么两棵树必然不会完全相同。

代码

  1. class Solution {
  2.     public boolean isSameTree(TreeNode p, TreeNode q) {
  3.         // 对应条件1，两个结点都为null, 返回true
  4.         if (p == null && q == null) {
  5.             return true;
  6.         }
  9.         // 对应条件2， 因为在上面的代码中，排除了两个都为null的情况
  10.         // 因此当下方if条件为true时，必然只有一个为null, 另一个不为null
  11.         if (p == null || q == null) {
  12.             return false;
  13.         }
  15.         // 对应条件3， 在上面的两段代码中，处理了都为null或者一个为null的情况
  16.         // 因此代码走到这里时，p和q都不是null
  17.         if (p.val != q.val) {
  18.             return false;
  19.         }
  21.         // 接着比较左子树和右子树
  22.         // 此时p.val == q.val, 接着去比较下一个结点
  23.         return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
  24.     }
  25. }