剑指Offer——把二叉树打印成多行

Question

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

Solution

• 用一个队列保存当前结点的孩子结点

• 然后要记录即将出队列结点的个数，因为会有新的节点入队列，所以要记录，然后一次遍历，这些节点的孩子又入队列。

Code

/*
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) {
        	if (pRoot == NULL)
                return vector<vector<int>>();
            queue<TreeNode*> Q;
            Q.push(pRoot);
            vector<vector<int>> res;
            while (!Q.empty()) {
                int size = Q.size();
                vector<int> temp;
                for (int i = 0; i < size; i++) {
                    TreeNode* current = Q.front();
                    Q.pop();
                    temp.push_back(current->val);
                    if (current->left != NULL)
                        Q.push(current->left);
                    if (current->right != NULL)
                        Q.push(current->right);
                }
                res.push_back(temp);
            }
            
            return res;
        }
    
};