검지offer-지그재그 인쇄 두 갈래 나무

메서드 1, 계층 인쇄, 짝수 행 반전,

 vector<vector<int>> Print(TreeNode* root) 
{
    queue q;
    vector<vector<int> > V;
    if(root==nullptr)return V;
    q.push(root);
    int even = 0;
    while(!q.empty())
    {
        vector<int> tmp;// 
        int n = q.size();
        while(n--)
        {
            root = q.front();
            tmp.push_back(root->val);
            if(root->left)q.push(root->left);
            if(root->right)q.push(root->right);
             q.pop();
        }
        if(even)
            reverse(tmp.begin(), tmp.end());
        even = !even;
        V.push_back(tmp);
    }
    return V;
}

방법 2. 두 개의 창고로 서로 다른 층의 노드를 저장한다

 vector<vector<int>> Print(TreeNode* root) 
{

    vector<vector<int> > V;
    if(root==nullptr)return V;
    stacks1,s2;  // s1, s2
    s1.push(root);
    while(!s1.empty()||!s2.empty())
    {
        if(!s1.empty())
        {
            vector<int> tmp;
            while(!s1.empty())        
            {
                TreeNode *root = s1.top();
                s1.pop();
                tmp.push_back(root->val);
                if(root->left)s2.push(root->left);
                if(root->right)s2.push(root->right);
            }
            V.push_back(tmp);
        }
        if(!s2.empty())
        {
            vector<int> tmp;
            while(!s2.empty())
            {
                TreeNode *root = s2.top();
                s2.pop();
                tmp.push_back(root->val);
                if(root->right)s1.push(root->right);// 
                if(root->left)s1.push(root->left);
            }
            V.push_back(tmp);
        }
    }
    return V;
}