《代码随想录网站》— 二叉树题目 — 8.对称二叉树 — 还可以用层次遍历

[Aapolaris]

题目链接

《代码随想录》网站链接

这道题，随想录提到只能用后序遍历做。

实际上还可以用层次遍历，但是要开辟额外的空间。相比较后序遍历，算是一种次优解吧。

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        queue<struct TreeNode*>q;
        q.push(root);
        while(!q.empty()){
            int size = q.size();
            vector<struct TreeNode*>vec;
            while(size--){
                struct TreeNode* cnt = q.front();
                q.pop();
                if(cnt->left)   q.push(cnt->left);
                if(cnt->right)  q.push(cnt->right);
                vec.push_back(cnt->left);
                vec.push_back(cnt->right);
            }
            int i=0, j=vec.size()-1;
            while(i<j){
                if(vec[i]!=NULL && vec[j]!=NULL){
                    if(vec[i]->val != vec[j]->val)  return false;
                }
                else if(vec[i] != vec[j])   return false; 
                i++;
                j--;
            }
        }
        return true;
    }
};