题目描述：

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

提示：
两棵树上的节点数目都在范围 [0, 100] 内
-10⁴ <= Node.val <= 10⁴

题解：

解题思路：

思路一（DFS）：

1、首先将两个树同时遍历结点的情况进行分析

• 两个节点为空 (nullptr) 返回 true，也就是指针唯一相同的情况
• 两个结点中有一个不存在，不是相同的树（返回false）
• 两个结点都存在，值不同则不是相同的树（返回false），值相同则是相同的树（继续查找）
• 对两个子树进行判断，若有一侧不是相同的树，则两颗树不是相同的树。

2、复杂度分析：
① 时间复杂度：O(n)，n代表树中结点的个数。
② 空间复杂度： O(n)，最坏的情况，即树的高度为节点数。

代码实现

代码实现（思路一（DFS））：

class Solution {
public:
    // 判断两棵树是否相同
    bool isSameTree(TreeNode* p, TreeNode* q) {
        // 如果两个节点都为空，说明这两棵树是相同的（都为空）
        if (p == q) {
            return true;
        }
        
        // 如果一个为空，另一个不为空，或者两个节点的值不同，则说明两棵树不同
        if ((q == nullptr && p != nullptr) || (q != nullptr && p == nullptr) || (q->val != p->val)) {
            return false;
        }
        
        // 递归检查左子树和右子树是否相同
        return (isSameTree(p->left, q->left) && isSameTree(p->right, q->right));
    }
};

以思路一为例进行调试

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

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){}

};

TreeNode *createTree(vector<int> &nums) {
    // 如果输入的数组为空，则返回空树
    if (nums.empty()) return nullptr;
    
    // 创建树的根节点，根节点的值为数组的第一个元素
    TreeNode *root = new TreeNode(nums[0]);
    
    // 使用队列来进行层序遍历，队列中存放的是树的节点
    queue<TreeNode *> Q;
    Q.push(root);  // 将根节点放入队列中
    int i = 1;     // 从数组的第二个元素开始处理

    // 遍历数组，构建树
    while (i < nums.size()) {
        // 取出队列中的当前节点
        TreeNode* node = Q.front();
        Q.pop();
        
        // 如果当前节点的左子节点不为空，创建左子节点
        if (i < nums.size() && nums[i] != -1) {
            node->left = new TreeNode(nums[i]);  // 创建左子节点
            Q.push(node->left);  // 将左子节点加入队列，等待进一步处理
        }
        i++;  // 移动到下一个数组元素

        // 如果当前节点的右子节点不为空，创建右子节点
        if (i < nums.size() && nums[i] != -1) {
            node->right = new TreeNode(nums[i]);  // 创建右子节点
            Q.push(node->right);  // 将右子节点加入队列，等待进一步处理
        }
        i++;  // 移动到下一个数组元素
    }
    
    // 返回构建好的二叉树的根节点
    return root;
}

class Solution {
public:
    // 判断两棵树是否相同
    bool isSameTree(TreeNode* p, TreeNode* q) {
        // 如果两个节点都为空，说明这两棵树是相同的（都为空）
        if (p == q) {
            return true;
        }
        
        // 如果一个为空，另一个不为空，或者两个节点的值不同，则说明两棵树不同
        if ((q == nullptr && p != nullptr) || (q != nullptr && p == nullptr) || (q->val != p->val)) {
            return false;
        }
        
        // 递归检查左子树和右子树是否相同
        return (isSameTree(p->left, q->left) && isSameTree(p->right, q->right));
    }
};

int main(int argc, char const *argv[])
{
    vector<int> nums1={1,2,3};
    vector<int> nums2={1,2,3};
    TreeNode *p = createTree(nums1);
    TreeNode *q = createTree(nums2);
    Solution s;
    if(s.isSameTree(p,q)){
        cout<<"true";
    }else{
        cout<<"false";
    }
    return 0;
}

LeetCode 面试经典 150_二叉树_相同的树（68_100)原题链接
欢迎大家和我沟通交流(✿◠‿◠)