题解 | #按之字形顺序打印二叉树#

/*
//缝缝补补了大半天，搞的代码，因为第一次使用嵌套的VECTOR，按照数组的逻辑来看已经不行了。
但是他们确实有相同之处，比如一个已知大小的vector<vector<int>> 类型的变量x可以通过auto p=x.begin(),
然后可以通过p[i][j],来读取任何一个该矩阵中的值，只是不想数组那样可以使用**p,因为本质上p是一个对象，
*p的返回值是vector<int>类型的对象，所以不能再解引用。虽然看起来变麻烦了，但也有变简单的部分，
就是可以不定义迭代器，往矩阵中增添元素。
2023/9/22

*/


/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > Print(TreeNode* pRoot) {
                //需要两个变量，一个整形变量，记录数的层数
                //一个指针，指向该层数的最后一个变量。
                //基数层数进入队列，偶数层数进入堆栈

// 1.0版本的失败，1.0需要一个堆栈和队列来解决，但是好像发现其实一个堆栈就行了
//只需要根据层数的基偶性来选择先push左节点还是右节点就行了。

                
                int level=1,j=-1;
                
                stack<TreeNode *> a1,a2;
                vector<vector<int>> ab;
                auto out=ab.begin();
                  
                ////////以上为定义区////////

                if(!pRoot)
                return ab;
                a1.push(pRoot);
                 while(!a1.empty()||!a2.empty())
                 {
///////////////////////////////////////////////////////////////////////////////                   

                    if(level%2==1)        //在奇数层，上一层的顺序是从右往左
                    //基数是从左往右，先压右
                    {
                        ab.push_back(vector<int>());
                        while(!a1.empty())
                        {
                            if(a1.top()->left)
                            a2.push(a1.top()->left);
                            if(a1.top()->right)
                            a2.push(a1.top()->right);

                        

                           ab.back().push_back(a1.top()->val);
                            a1.pop();
                            j++;
                        }
                    }level++;j=0;
  ///////////////////////////////////////////////////////////////////////////////

                        if(level%2==0)//上一层基数层是从左往右
                    //所以这层就要先压左
                    {
                        if(!a2.empty())
                        ab.push_back(vector<int>());
                        while(!a2.empty())
                        {
                             if(a2.top()->right)
                            a1.push(a2.top()->right);
                            if(a2.top()->left)
                            a1.push(a2.top()->left);
                           
     
                            ab.back().push_back(a2.top()->val);
                            a2.pop();
                            j++;
                        }
                    }level++;j=0;




                 }
                 return ab;


   
    }
};