劍指offer-60. 把二叉樹列印成多行

題目描述

從上到下按層列印二叉樹，同一層結點從左至右輸出。每一層輸出一行。

解題思路：

1.把二叉樹的根結點存入隊列

2.如果存在子結點，子結點插入到隊尾

3.從隊首取出元素存入容器中

4.用兩個變量記錄目前層的結點數和下一層的結點數

5.目前層周遊結束時，目前層結點數為0，把該層結點存入vector中，繼續進行下一層的周遊

6.循環上述過程直到隊列為空

代碼實作：

/*
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) {
         /*
        解題思路：
        1.把二叉樹的根結點存入隊列
        2.如果存在子結點，子結點插入到隊尾
        3.從隊首取出元素存入容器中
        4.用兩個變量記錄目前層的結點數和下一層的結點數
        5.目前層周遊結束時，目前層結點數為0，把該層結點存入vector中，繼續進行下一層的周遊
        6.循環上述過程直到隊列為空
        */
        vector<int> result;
        vector<vector<int> > ans;
        int currentCount = 0,nextCount = 0;
        if(pRoot == NULL){
            return ans;
        }
        queue<TreeNode*> q;
        TreeNode* currentNode;
        q.push(pRoot);
        currentCount++;
        while(!q.empty()){
            currentNode = q.front();
            result.push_back(currentNode->val);
            q.pop();
            currentCount--;
            
            if(currentNode->left != NULL){
                q.push(currentNode->left);
                nextCount++;
            }
            if(currentNode->right != NULL){
                q.push(currentNode->right);
                nextCount++;
            }
            
            if(currentCount == 0){
               ans.push_back(result); 
               result.clear();
               currentCount = nextCount;
               nextCount = 0;
            }
            
        }
        return ans;
    }
        
    
};
           

 效率：