By

题目描述

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

题目解析

很明显的层序遍历二叉树，BFS算法。用一个队列来保存层序遍历的数据，last指针指向上层的最后一个元素，nlast指针为移动指针，在上一层中移动，并将nlast的值加入到vec_son，同时将nlast的左右儿子加入到队列中来。当nlast移动到last时，表示上一层已经遍历结束，将vec_son加入到vec_father中，last指向队尾，nlast继续往下遍历，直到队列遍历结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/*
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) {
            //this is a BFS algorithm.
            //create a queue to save data.
            TreeNode* queue[510];
             
            TreeNode* last=pRoot;
            TreeNode* nlast=pRoot;
             
            vector<int> vec_son;
            vector<vector<int>> vec_father;
             
            queue[0]=pRoot;
             
            for(int i=1,j=1;queue[j-1]!=NULL;){
                vec_son.push_back(nlast->val);
                if(nlast->left!=NULL){
                    queue[i++]=nlast->left;
                }
                if(nlast->right!=NULL){
                    queue[i++]=nlast->right;
                }
                if(nlast==last){
                    last=queue[i-1];
                    vec_father.push_back(vec_son);
                    vec_son.clear();
                }
                nlast=queue[j++];
            }
            return vec_father;
        }
};