题目描述
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
实现
/**
* 层序遍历
*/
public static List<List<String>> levelOrder(TreeNode<String> root) {
//存储各个节点的内容
List<List<String>> levelNodeDataList = new LinkedList<>();
if (root != null) {
//把"当前层节点"和"下一层节点"全部存到一个"队列"中,当前层的节点添加到队列的前边,下一层节点添加到队列的尾部
//遍历队列的时候,需要知道"当前层和下一层的"分界点,需要在遍历前保存一个"当前队列"的容量(此时还没添加下一层节点,所以仅仅包含当前层节点的个数)
//用"队列的链式存储结构(不用顺序结构)"节省内存(顺序存储结构的话(ArrayList)内部使用动态数组的方式实现,会有一部分无用内存的浪费)
Queue<TreeNode<String>> curLevelNodeList = new LinkedList<>();
curLevelNodeList.add(root);
while (!curLevelNodeList.isEmpty()) {
//记录下当前层有多少个节点
int curNodeSize = curLevelNodeList.size();
//存储当前层的节点数据
LinkedList<String> curLevelNodeDataList = new LinkedList<>();
for (int i = 0; i < curNodeSize; i++) {
TreeNode<String> node = curLevelNodeList.poll();
if (node != null) {
//
curLevelNodeDataList.add(node.data);
//
if (node.left != null) {
curLevelNodeList.add(node.left);
}
//
if (node.right != null) {
curLevelNodeList.add(node.right);
}
}
}
levelNodeDataList.add(curLevelNodeDataList);
}
}
return levelNodeDataList;
}
