牛客各种输入输出例子

树系列 主要是熟悉根据给定数据格式建立二叉树

二叉树按层打印与zigzag打印

#include<bits/stdc++.h>
using namespace std;
struct TreeNode{
    TreeNode* left;
    TreeNode* right;
    int val;
    TreeNode(int v):val(v),left(nullptr),right(nullptr){}
};
//先序建树
void createTree(TreeNode* root,int N){
    if(!N) return;
    int p,l,r;
    cin>>p>>l>>r;
    if(l){
        root->left = new TreeNode(l);
        createTree(root->left, N-1);
    }
    if(r){
        root->right = new TreeNode(r);
        createTree(root->right,N-1);
    }
}
void levelPrint(TreeNode* root){
    if(!root) return;
    queue<TreeNode*>q;
    q.push(root);
    int depth = 1;
    while(!q.empty()){
        int len = q.size();
        cout<<"Level "<<depth<<" :";
        for(int i=0;i<len;++i){
            TreeNode* cur = q.front();
            q.pop();
            cout<<" "<<cur->val;
            if(cur->left)
                 q.push(cur->left);
            if(cur->right)
                q.push(cur->right);
        }
        cout<<endl;
        ++depth;
    }
}
void zigzagPrint(TreeNode* root){
    if(!root) return;
    //普通队列即可
    //不用整双端队列
    queue<TreeNode*>q;
    q.push(root);
    int depth = 1;
    //标记位 记录当前从哪个方向开始打印
    int flag = 1;
    while(!q.empty()){
        int len = q.size();
        vector<int>v;
        for(int i=0;i<len;++i){
            TreeNode* cur = q.front();
            //记得出队 
            q.pop();
            v.push_back(cur->val);
            if(cur->left)
                q.push(cur->left);
            if(cur->right)
                q.push(cur->right);
        }
        if(flag){
            //从左到右
            cout<<"Level "<<depth<<" from left to right:";
            for(int j=0;j<v.size();++j)
                cout<<" "<<v[j];
        }
        else{
            cout<<"Level "<<depth<<" from right to left:";
            for(int j=v.size()-1;j>=0;--j)
                cout<<" "<<v[j];
        }
        //更新标记位
        flag = !flag;
        //增加深度
        depth++;
        cout<<endl;
    }
}
int main(){
    int N,root_val;
    TreeNode* root = nullptr;
    cin>>N>>root_val;
    root = new TreeNode(root_val);
    createTree(root, N);
    levelPrint(root);
    zigzagPrint(root);
    return 0;
}