题目链接

题目描述：

给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

100相同的树 - 图1

解题思路

  本题与#101类似，题解在此～

  1. 观察本题，要求对比两个树是否完全相同，主函数给出了两个参数(也就是两个树的根结点)，可能就不需要辅助函数扩展参数列表了。
  2. 确定两个递归终止条件：一、显然两结点同时为空，那么肯定是相同了；二、如果在两结点中，一个为空，另一个不为空，显然不相同。注意：代码顺序不要改变，因为情况1用到的逻辑运算符为&&，情况2用到的逻辑运算符为||，显然2在1之前会涵盖1的情况。其实，本质上来说，情况2属于异或
  3. 剩下的代码本质上来说就是先序遍历的递归框架

代码

  1. class Solution {
  2. public:
  3.     bool isSameTree(TreeNode* p, TreeNode* q) {
  4.         if(!p && !q)
  5.             return true;
  6.         if((p==NULL) || (q==NULL))
  7.             return false;
  8.         if(p->val != q->val)
  9.             return false;
  10.         return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
  11.     }
  12. };