Same Tree

100. 相同的树

分析

递归判断根节点：首先检查两个根节点 p 和 q 的值是否相等，如果它们相等，就继续递归地检查它们的左右子树
递归判断左右子树：分别递归比较 p 的左子树与 q 的左子树，p 的右子树与 q 的右子树
递归的终止条件：
- 如果两个节点都为空，说明它们相等
- 如果两个节点其中一个为空，或者它们的值不相等，返回 false
最终结果：只有当根节点和左右子树都完全相同的情况下，两棵树才是相同的

时间复杂度

时间复杂度 O(n)

空间复杂度

空间复杂度为 O(h)，h 是树的高度

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution
{
public:
    bool isSameTree(TreeNode* p, TreeNode* q)
    {
        // 如果 p 和 q 都为空，说明它们是相同的
        if (!p && !q)
            return true;

        // 如果 p 和 q 其中一个为空，或它们的值不同，返回 false
        if (!p || !q || p->val != q->val)
            return false;

        // 递归地比较左右子树
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};