题目描述:
从上到下按层打印二叉树,同一层结点从左至右输出。每一层输出一行。
解题思路:
这道题比《剑指Offer》按之字顺序打印二叉树简单一些。思路和上一道题一样,区别在于,这把是先入先出,使用队列即可。
按层次输出二叉树。
访问根节点,并将根节点入队。
当队列不空的时候,重复以下操作。
弹出一个元素。作为当前的根节点。
如果根节点有左孩子,访问左孩子,并将左孩子入队。
如果根节点有右孩子,访问右孩子,并将右孩子入队。
代码实现(c++)
/*
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) {
vector<vector<int>> res;
if (pRoot == nullptr) return res;
queue<TreeNode*> q;
q.emplace(pRoot);
while (!q.empty()){
vector<int> tmp;
int size = q.size();
for (int i = 0; i < size; ++i){
auto cur = q.front();
q.pop();
tmp.emplace_back(cur->val);
if (cur->left) q.emplace(cur->left);
if (cur->right) q.emplace(cur->right);
}
res.emplace_back(tmp);
}
return res;
}
};
代码实现(java)
import java.util.*;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> layers = new ArrayList<ArrayList<Integer>>();
if (pRoot == null)
return layers;
Deque<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(pRoot);
while (!queue.isEmpty()) {
ArrayList<Integer> layer = new ArrayList<Integer>();
int cur = 0, size = queue.size();
while (cur < size) {
TreeNode node = queue.poll();
layer.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
cur ++;
}
layers.add(layer);
}
return layers;
}
}