剑指offer面试题[60]-将二叉树打印成多行

梦里梦外; 2022-06-11 01:09 98阅读 0赞

## 题目描述 ##

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

/*
    struct TreeNode {
        int val;
        struct TreeNode *left;
        struct TreeNode *right;
        TreeNode(int x) :
                val(x), left(NULL), right(NULL) {
        }
    };
    */
    class Solution {
    public:
            vector<vector<int> > Print(TreeNode* pRoot) {              
               deque<TreeNode*> PrintOnLayer;
               vector<vector<int> > res;
               if(pRoot==NULL)            //需判断树是否为空
                   return res;
               vector<int> vec;
               PrintOnLayer.push_back(pRoot);
               
               int toBePrint=1;           //表示当前层中还有没有打印的结点
               int NextLayerNode=0;       //下一层结点的数目
                           
               while(!PrintOnLayer.empty())
                  {
                     TreeNode* pNode=PrintOnLayer.front();
                     PrintOnLayer.pop_front();
                    
                     vec.push_back(pNode->val);
                     toBePrint--;
                    
                     if(pNode->left)          //注意NextLayerNode在该层未打印完之前，若被打印的两个结点分别左右子节点，
                       {                      //NextLayerNode会增加到4。。。注意理解
                          NextLayerNode++;      
                          PrintOnLayer.push_back(pNode->left);   
                       }
                     if(pNode->right)
                       {
                          NextLayerNode++;
                          PrintOnLayer.push_back(pNode->right);   
                       }  
                     if(toBePrint==0)
                       {
                          toBePrint=NextLayerNode;
                          NextLayerNode=0;
                          
                          res.push_back(vec);         //将每一层的数以vecror的形式存取到res中
                          vec.clear();               //每一层打印完毕后需要将vec清除
                       }
                  }
                return res;
            }  
    };