从上到下打印二叉树(剑指Offer-32.1)

题面

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

例如: 给定二叉树: [3,9,20,null,null,15,7],

1    3
2   / \
3  9  20
4    /  \
5   15   7

返回：

1[3,9,20,15,7]

限制

1节点总数 <= 1000

思路

BFS层序遍历。

代码

 1/**
 2 * Definition for a binary tree node.
 3 * struct TreeNode {
 4 *     int val;
 5 *     TreeNode *left;
 6 *     TreeNode *right;
 7 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8 * };
 9 */
10class Solution {
11public:
12    vector<int> levelOrder(TreeNode* root) {
13        vector<int> v;
14        if(root==NULL) return v;
15
16        queue<TreeNode *>q;
17        q.push(root);
18
19        while(!q.empty()){
20            TreeNode *t = q.front(); q.pop();
21            v.push_back(t->val);
22            if(t->left)
23                q.push(t->left);
24            if(t->right)
25                q.push(t->right);
26        }
27        return v;
28    }
29};