100. 相同的树#

题目#

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

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

5

6
示例 1：
7

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

11
示例 2：
12

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

16
示例 3：
17

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

21
提示：
22

23
两棵树上的节点数目都在范围 [0, 100] 内
24
-10^4 <= Node.val <= 10^4

题目思路#

简单题，与昨日的解法类似，可以使用递归解决问题，也可以进行层序遍历，熟悉一下 BFS 的模板。

题目代码#

代码块#

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) :
10
        val(x), left(left), right(right) {}
11
 * };
12
 */
13
class Solution {
14
public:
15
    bool isSameTree(TreeNode* p, TreeNode* q) {
16
        /* if (p == nullptr && q == nullptr) {
17
            return true;
18
        } else if (p == nullptr || q == nullptr) {
19
            return false;
20
        } else if (p->val != q->val) {
21
            return false;
22
        } else {
23
            return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
24
        } */
25
        if (p == nullptr && q == nullptr) return true;
26
        else if (p == nullptr || q == nullptr) return false;
27
        queue <TreeNode*> q1, q2;
28
        q1.push(p);
29
        q2.push(q);
30
        while (q1.empty() == 0 && q2.empty() == 0) {
31
            auto n1 = q1.front();
32
            q1.pop();
33
            auto n2 = q2.front();
34
            q2.pop();
35
            if (n1 -> val != n2 -> val) return false;
36
            auto l1 = n1 -> left, r1 = n1 -> right, l2 = n2 -> left, r2 = n2 -> right;
37
            if ((l1 == nullptr) ^ (l2 == nullptr)) return false;
38
            if ((r1 == nullptr) ^ (r2 == nullptr)) return false;
39
            if (l1 != nullptr) q1.push(l1);
40
            if (r1 != nullptr) q1.push(r1);
41
            if (l2 != nullptr) q2.push(l2);
42
            if (r2 != nullptr) q2.push(r2);
43
        }
44
        return q1.empty() && q2.empty();
45
    }
46
};

复杂度#

时间复杂度：O(min(n, m))
空间复杂度：递归为 O(min(n, m))，调用栈使用的空间即为二叉树的高度；层序遍历为 O(n)，用于存放所有的节点数。