1. 知识点总结

题目	难度	知识点
对称二叉树	🐸	二叉树遍历
二叉树的层序遍历	🐸	二叉树的层序遍历

2. 分题题解

2.1 对称二叉树

没有想到比较好的降低空间的方法，另外说明一下-1的那个不加会wa的哈

执行用时：4 ms, 在所有 C++ 提交中击败了72.68%的用户

内存消耗：17 MB, 在所有 C++ 提交中击败了5.12%的用户

class Solution {
public:
    vector<int>a,b;
    void inTravel1(TreeNode* root){
        if(root==NULL){
            a.push_back(-1);
            return;
        }else{
            a.push_back(root->val);
            inTravel1(root->left);
            inTravel1(root->right);
        }
    }
    void inTravel2(TreeNode* root){
        if(root==NULL){
            b.push_back(-1);
            return;
        }else{
            b.push_back(root->val);
            inTravel2(root->right);
            inTravel2(root->left);
        }
    }
    bool isSymmetric(TreeNode* root) {
        inTravel1(root);
        inTravel2(root);
        for(int i=0;i<a.size();i++){
            if(a[i]!=b[i]){
                return false;
            }
        }
        return true;
    }
};

2.2 二叉树的层序遍历

emm因为没法直接在树的结点上加level信息，只好再重开一个并列的queue存储

class Solution {
public:
    vector<vector<int> >ans;
    int cnt=0;
    void levelTravel(TreeNode* root){
        //层次遍历
        queue<TreeNode*>q;
        queue<int>level;//记录层号
        int curl=1;
        q.push(root);
        level.push(curl);
        while(!q.empty()){
            TreeNode* topnode=q.front();
            int toplevel=level.front();
            //将当前结点加到vector中
            if(cnt<toplevel){
                ans.push_back({});
                cnt++;
            }
            ans[toplevel-1].push_back(topnode->val);
            //下一个
            if(topnode->left!=NULL){
                q.push(topnode->left);
                level.push(toplevel+1);
            }
            if(topnode->right!=NULL){
                q.push(topnode->right);
                level.push(toplevel+1);
            }
            q.pop();
            level.pop();
        }
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(root!=NULL){
            levelTravel(root);
        }

        return ans;
    }
};