从上到下按层打印二叉树,同一层结点从左至右输出。每一层输出一行。
给定的二叉树是{1,2,3,#,#,4,5}
:
该二叉树多行打印层序遍历的结果是:
[
[1],
[2,3],
[4,5]
]
示例1 输入
{8,6,10,5,7,9,11}
返回值
[[8],[6,10],[5,7,9,11]]
和前面的题差不多,甚至更加简单:
-
借助双向链表,先将根节点添加进去:
-
获取
list
里面剩下的元素的个数,挨个取出就是一层,取出的时候,添加到当前层的list
结果集中,然后判断每一个取出来的节点的左右节点是不是为空,不为空则加入链表。(按照层次遍历的时候需要按照size
来循环) -
每一层处理完之后,将
list
加入结果集中,继续判断list
是不是为空,执行第二步循环。
import java.util.ArrayList;
import java.util.LinkedList;
public class Solution60 {
ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> results = new ArrayList<>();
LinkedList<TreeNode> nodes = new LinkedList<>();
if (pRoot != null) {
nodes.add(pRoot);
while (!nodes.isEmpty()) {
ArrayList<Integer> integers = new ArrayList<>();
int size = nodes.size();
for (int i = 0; i < size; i++) {
TreeNode node = nodes.poll();
integers.add(node.val);
if (node.left != null) {
nodes.add(node.left);
}
if (node.right != null) {
nodes.add(node.right);
}
}
if (!integers.isEmpty()) {
results.add(integers);
}
}
}
return results;
}
}
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>> results;
deque<TreeNode *> nodes;
if (pRoot != NULL) {
nodes.push_back(pRoot);
while (nodes.size() > 0) {
vector<int> integers;
int size = nodes.size();
for (int i = 0; i < size; i++) {
TreeNode *node = nodes.front();
nodes.pop_front();
integers.push_back(node->val);
if (node->left != NULL) {
nodes.push_back(node->left);
}
if (node->right != NULL) {
nodes.push_back(node->right);
}
}
if (integers.size() > 0) {
results.push_back(integers);
}
}
}
return results;
}
};
借助了队列,空间复杂度为O(n)
,时间复杂度为O(n)
。