剑指 Offer 28. 对称的二叉树

题目链接

剑指 Offer 28. 对称的二叉树 easy

题目描述

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

例如，二叉树 [1,2,2,3,4,4,3]是对称的。

但是下面这个 [1,2,2,null,3,null,3]则不是镜像对称的:

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

提示：

• $0<=节点个数<=1000$

解法：递归

如果 $root$ 是 对称 的，那么它肯定如下特征(我们用 $p$ 表示 $root$ 的左子结点，用 $q$ 表示 $root$ 的右子结点)：

• $p.val==q.val$
• $p.left.val==q.right.val\&\&p.right.val==q.left.val$
• $p$ 和 $q$ 要么同时为空，要么同时不为空，不能出现一个为空 另一个不为空

时间复杂度： $O(n)$

C++代码：

class Solution {
public:bool dfs(TreeNode* p,TreeNode* q){if(p == nullptr && q == nullptr) return true;if(p == nullptr || q == nullptr || p->val != q->val) return false;return dfs(p->left,q->right) && dfs(p->right,q->left);}bool isSymmetric(TreeNode* root) {if(root == nullptr) return true;return dfs(root->left,root->right);}
};