题目

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

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

示例 1：
image.png

  1. 输入：p = [1,2,3], q = [1,2,3]
  2. 输出：true

示例 2：
image.png

输入：p = [1,2], q = [1,null,2]
输出：false

示例 3：
image.png

输入：p = [1,2,1], q = [1,1,2]
输出：false

提示：

  • 两棵树上的节点数目都在范围 [0, 100] 内

  • -10^4 <= Node.val <= 10^4

    解题方法

    递归 DFS

    通过递归 DFS 对比两棵树的各节点。
    时间复杂度O(min(m,n))，空间复杂度O(min(m,n))
    C++代码：

    /**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
  bool isSameTree(TreeNode* p, TreeNode* q) {
      if(!p && !q)    return true;
      else if(!p || !q)  return false;
      else if(p->val != q->val)   return false;
      else return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
  }
};

    迭代 BFS

    通过迭代遍历二叉树各节点。
    时间复杂度O(min(m,n))，空间复杂度O(min(m,n))
    C++代码：

    /**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
  bool isSameTree(TreeNode* p, TreeNode* q) {
      if(!p && !q)    return true;
      else if(!p || !q)   return false;
      queue<TreeNode*> p_nodes, q_nodes;
      p_nodes.push(p);
      q_nodes.push(q);
      while(p_nodes.size()>0 && q_nodes.size()>0) {
          TreeNode *p_cur, *q_cur;
          p_cur = p_nodes.front(); p_nodes.pop();
          q_cur = q_nodes.front(); q_nodes.pop();
          if(p_cur->val != q_cur->val)    return false;
          if((!p_cur->left && q_cur->left) || (p_cur->left && !q_cur->left))  return false;
          if((!p_cur->right && q_cur->right) || (p_cur->right && !q_cur->right))  return false;
          if(p_cur->left) p_nodes.push(p_cur->left);
          if(p_cur->right) p_nodes.push(p_cur->right);
          if(q_cur->left) q_nodes.push(q_cur->left);
          if(q_cur->right) q_nodes.push(q_cur->right);
      }

      return p_nodes.size()==0 && q_nodes.size()==0;
  }
};