leetcode hot100刷题日记——27.对称二叉树

方法一：递归法

class Solution {
public:bool check(TreeNode *left,TreeNode *right){//左子树和右子树的节点同时是空的是对称的if(left==nullptr&&right==nullptr){return true;}if(left==nullptr||right==nullptr){return false;}//检查左右子树的值相不相等，再检查左子树的左节点是不是和右子树的右节点相同，左子树的右节点是不是和右子树的左节点相同return left->val==right->val&&check(left->left,right->right)&&check(left->right,right->left);}bool isSymmetric(TreeNode* root) {return check(root->left,root->right);}
};

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

方法二：迭代法，用队列

class Solution {
public:bool check(TreeNode *u,TreeNode *v){queue<TreeNode*>q;q.push(u);q.push(v);while(!q.empty()){u=q.front();q.pop();v=q.front();q.pop();if(!u&&!v) continue;if((!u||!v)||(u->val!=v->val)) return false;q.push(u->left);q.push(v->right);q.push(u->right);q.push(v->left);}return true;}bool isSymmetric(TreeNode* root) {return check(root,root);}
};

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