Day97 | 灵神 | 二叉树 对称二叉树

101.对称二叉树

101. 对称二叉树 - 力扣（LeetCode）

思路：

和上一题的区别就是在p和q值相同的时候递归遍历的下一棵子树不同

上一题是左子树和左子树，右子树和右子树对比

这一题的对称就是左子树的左子树和右子树的右子树，左子树的右子树和右子树的左子树对比

不同的情况是

1.p为空q不为空

2.p不为空q为空

3.pq值不同

相同的情况是

pq均为空

注：pq值相同不能说明是true，还要看pq的左右子树

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool is(TreeNode *l,TreeNode *r)
    {
        if(l==nullptr&&r!=nullptr)
            return false;
        else if(l!=nullptr&&r==nullptr)
            return false;
        else if(l==nullptr&&r==nullptr)
            return true;
        else if(l->val==r->val)
            return is(l->left,r->right) && is(l->right,r->left);
        else
            return false;
    }
    bool isSymmetric(TreeNode* root) {
        if(root==nullptr)
            return true;
        return is(root->left,root->right);
    }
};

灵神的简洁版代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    // 在【100. 相同的树】的基础上稍加改动
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == nullptr || q == nullptr) {
            return p == q;
        }
        return p->val == q->val && isSameTree(p->left, q->right) && isSameTree(p->right, q->left);
    }

public:
    bool isSymmetric(TreeNode* root) {
        return isSameTree(root->left, root->right);
    }
};