题目链接

题目描述

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

示例

示例1：

image.png

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

提示

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

  • -104 <= Node.val <= 104

    思路

    深搜即可

    题解

    1. /**
    2. * Definition for a binary tree node.
    3. * struct TreeNode {
    4. *     int val;
    5. *     TreeNode *left;
    6. *     TreeNode *right;
    7. *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    8. *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    9. *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    10. * };
    11. */
    12. class Solution {
    13.  public:
    14.   bool isSameTree(TreeNode *p, TreeNode *q) {
    15.       if (p == nullptr && q == nullptr) {
    16.           return true;
    17.       } else if (p == nullptr || q == nullptr) {
    18.           return false;
    19.       } else if (p->val != q->val) {
    20.           return false;
    21.       } else {
    22.           return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    23.       }
    24.   }
    25. };

    复杂度分析

  • 时间复杂度：0100-相同的树 - 图2

  • 空间复杂度：0100-相同的树 - 图3