堂兄弟结点父不同

class Solution {
public:
    unordered_map<int,int>level;
    unordered_map<int,int>fa;
    bool isCousins(TreeNode* root, int x, int y) {
        queue<TreeNode*>q;q.push(root);int cur=0;
        while(q.size()){
            int n=q.size();
            while(n--){
            auto t=q.front();q.pop();
            level[t->val]=cur;
            if(t->left){fa[t->left->val]=t->val;q.push(t->left);}
            if(t->right){fa[t->right->val]=t->val;q.push(t->right);}
            }
            cur++;//计算层数
        }
        if(level[x]==level[y]&&fa[x]!=fa[y])return true;
        return false;
    }
};
扩展求和 每个点更改为堂节点的和
class Solution {
public:
    void bfs(TreeNode*root){
        queue<TreeNode*>q;
        q.push(root);
        while(q.size()){
            int sum=0;//下一层结点和
            int n=q.size();
            vector<TreeNode*>tmp;//当前层结点

            for(int i=0;i<n;i++){
                TreeNode*t=q.front();q.pop();  tmp.push_back(t);
                if(t->left){sum+=t->left->val;q.push(t->left);}
                if(t->right){sum+=t->right->val;q.push(t->right);}
            }
            for(auto fa:tmp){
                int sub=(fa->left?fa->left->val:0)+(fa->right?fa->right->val:0);
                if(fa->left)fa->left->val=sum-sub;//更新
                if(fa->right)fa->right->val=sum-sub;//当前层结点和减去自身fa子结点和
            }
        }

    }
    TreeNode* replaceValueInTree(TreeNode* root) {
        root->val=0;
        bfs(root);
        return root;
   }
};

锯齿遍历

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>>ans;
        queue<TreeNode*>q;
        if(!root)return ans;
        q.push(root);
        int cnt=0;
        while(q.size()){         
            vector<int>level;
            int n=q.size();
            while(n--){
                TreeNode*t=q.front();
                q.pop();
                level.push_back(t->val);
                if(t->left)q.push(t->left);
                if(t->right)q.push(t->right);
            }
            if(++cnt%2==0)reverse(level.begin(),level.end());
            ans.push_back(level);
        }
        return ans;
    }
};
层平均值
vector<double> averageOfLevels(TreeNode* root) {
        vector<double>ans;
        queue<TreeNode*>q;
        if(!root)return ans;
        q.push(root);
        while(q.size()){
            int n=q.size();
            double sum=0;
            for(int i=0;i<n;i++){
                auto t=q.front();q.pop();
                sum+=t->val;
                if(t->left)q.push(t->left);
                if(t->right)q.push(t->right);
            }
            ans.push_back(sum/=n);
        }
        return ans;
    }

二叉树垂直遍历

利用pair存放结点信息

class Solution {
public: vector<vector<int>>ans;
    int leftboard=0,rightboard=0;
    //求最左最右宽度
    void dfs(TreeNode*root,int board){
        if(!root)return;
        leftboard=min(leftboard,board);
        rightboard=max(rightboard,board);
        dfs(root->left,board-1);
        dfs(root->right,board+1);
    }

    vector<vector<int>> verticalOrder(TreeNode* root) {
        if(!root)return ans;
        dfs(root,0);
        ans.resize(rightboard-leftboard+1);
        queue<pair<TreeNode*,int>>q;
        q.push({root,-leftboard});//根据水平距离存放答案
        while(!q.empty()){
            int n=q.size();
            while(n--){
                ans[q.front().second].push_back(q.front().first->val);
                if(q.front().first->left)q.push({q.front().first->left,q.front().second-1});
                if(q.front().first->right)q.push({q.front().first->right,q.front().second+1}); 
                q.pop();
            }          
        }
        return ans;
    }
};

垂序遍历 从左往右列再按行 如果两者相等 按权大小

class Solution {
public:

    map<int,vector<vector<int>>>S;//第一个代表列第二个代表行权
    void dfs(TreeNode*root,int x,int y){
        if(!root)return;
        S[y].push_back({x,root->val});
        dfs(root->left,x+1,y-1);
        dfs(root->right,x+1,y+1);
    } 
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        dfs(root,0,0);
        vector<vector<int>>res;//存放答案
        for(auto&[k,v]:S){//遍历每一列
           sort(v.begin(),v.end());
           vector<int>col;
           for(auto&p:v) col.push_back(p[1]);//p[0]p[1]是行权
           res.push_back(col);
        }
        return res;
    }
};

二叉树对称反转

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