题目描述
给定一个二叉树，检查它是否是镜像对称的。
示例：
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/
2 2
/ /
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/
2 2
3 3
题目链接： https://leetcode-cn.com/problems/symmetric-tree/
思路1
使用递归。如果一个二叉树是对称的，则根结点左子树的值==根结点右子树的值，根结点左子树的左子树的值==根结点右子树的右子树的值，根结点左子树的右子树的值==根结点右子树的左子树的值。代码如下：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(root==nullptr) return true;
TreeNode* leftTree = root->left;
TreeNode* rightTree = root->right;
return isEqual(leftTree, rightTree);
}
bool isEqual(TreeNode* leftTree, TreeNode* rightTree){
if(leftTree==nullptr){
if(rightTree==nullptr) return true;
else return false;
}else if(rightTree==nullptr){
if(leftTree==nullptr) return true;
else return false;
}
return (leftTree->val==rightTree->val) && isEqual(leftTree->left, rightTree->right) && isEqual(leftTree->right, rightTree->left);
}
};
- 时间复杂度：O(n)
- 空间复杂度：O(h)
h为树的高度。
思路2
使用bfs。将输入的树看成两棵相同的树，一棵树从左往右将每层的节点加入队列，另一棵树从右往左将每层的节点加入队列。在出队列的时候，判断出队列的两个连续的节点值是否相同。代码如下：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(root==nullptr) return true;
queue<TreeNode*> q;
q.push(root);
q.push(root);
while(!q.empty()){
TreeNode* node1 = q.front(); q.pop();
TreeNode* node2 = q.front(); q.pop();
if(node1==nullptr && node2==nullptr) continue; //注意这里是continue，不是return true;
if(node1==nullptr || node2==nullptr) return false;
if(node1->val!=node2->val) return false;
q.push(node1->left);
q.push(node2->right);
q.push(node1->right);
q.push(node2->left);
}
return true;
}
};
- 时间复杂度：O(n)
- 空间复杂度：O(n)(最坏情况下)