10-2 相同的树（leecode 100）1 问题2 解法

72 阅读 0 评论 48 点赞

我是靠谱客的博主健忘母鸡，这篇文章主要介绍10-2 相同的树（leecode 100）1 问题2 解法，现在分享给大家，希望可以做个参考。

1 问题

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

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
在这里插入图片描述输入：p = [1,2,3], q = [1,2,3]
输出：true

2 解法

复制代码

/**
 * 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 compare(TreeNode* a, TreeNode* b)
    {
        //2.递归结束条件
        //a,b都为空
        if(a == nullptr && b == nullptr)    
            return true;
        //a为空，b不为空
        else if(a == nullptr && b != nullptr)
            return false;
        //a不为空，b为空
        else if(a != nullptr && b == nullptr)
            return false;
        //a,b都不为空，但值不等
        else if(a->val != b->val)
            return false;
        //3.每层递归的逻辑
        //a,b都不为空，且值相等
        else
        {
            //比较a，b的左侧
            bool left = compare(a->left, b->left);
            //比较a，b的右侧
            bool right = compare(a->right, b->right);
            return left && right;
        }
    }
    bool isSameTree(TreeNode* p, TreeNode* q) {
        return compare(p, q);
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * 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 compare(TreeNode* a, TreeNode* b)
    {
        //2.递归结束条件
        //a,b都为空
        if(a == nullptr && b == nullptr)    
            return true;
        //a为空，b不为空
        else if(a == nullptr && b != nullptr)
            return false;
        //a不为空，b为空
        else if(a != nullptr && b == nullptr)
            return false;
        //a,b都不为空，但值不等
        else if(a->val != b->val)
            return false;
        //3.每层递归的逻辑
        //a,b都不为空，且值相等
        else
        {
            //比较a，b的左侧
            bool left = compare(a->left, b->left);
            //比较a，b的右侧
            bool right = compare(a->right, b->right);
            return left && right;
        }
    }
    bool isSameTree(TreeNode* p, TreeNode* q) {
        return compare(p, q);
    }
};