题目描述
Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
解题思路
题目要就即实现二叉树的层次遍历，类似的还有前序(DLR)、中序(LDR)、后序(LRD)遍历，后三种使用递归很容易实现，同样也可以利用栈来辅助以实现非递归算法，有些实现起来可能比较麻烦。这里我们要求层次遍历，利用辅助队列来实现层次遍历，由于这里输出的要求是按层次的，我们记录节点的层次信息，同一层次的遍历的时候(从队列里弹出的时候)放到一个集合里，遍历完一个层次之后将该层子节点集合加入到 List
详细代码
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
//Binary Tree Level Order Traversal
//自定义带有层次信息的节点信息结构
class TreeNodeWithDepth
{
TreeNode treeNode;
int depth;
public TreeNodeWithDepth(TreeNode treeNode, int depth)
{
this.treeNode = treeNode;
this.depth = depth;
}
}
public List
> levelOrder(TreeNode root) { int depth = 1; int lastLevel = 1; //while中用来标示上一次节点的level List
> resultsList = new ArrayList
>(); //注意初始化 List是接口类 Queue
queue = new LinkedList<>(); TreeNodeWithDepth pNode = null; if(root != null) { pNode = new TreeNodeWithDepth(root, 1); queue.offer(pNode); } List
listPerLevel = new ArrayList<>();//每层的list while(!queue.isEmpty()) { pNode = queue.poll();//程序加入时已经判断不为空节点 if(pNode.depth > lastLevel) { //说明是新的一层 if(listPerLevel.size()!=0) { //把上一层的列表加入result中 resultsList.add(listPerLevel); } listPerLevel = new ArrayList<>(); //重新另起一个listPerLevel listPerLevel.add(pNode.treeNode.val);//在新列表中加入当前节点 lastLevel = pNode.depth;//更新lastLevel } else { listPerLevel.add(pNode.treeNode.val); } //确定子节点深度 depth = pNode.depth+1; //子节点入队列 if(pNode.treeNode.left != null) { queue.offer(new TreeNodeWithDepth(pNode.treeNode.left, depth)); } if(pNode.treeNode.right != null) { queue.offer(new TreeNodeWithDepth(pNode.treeNode.right, depth)); } } //while循环中最后一次的listPerLevel也要加入 if(listPerLevel.size()>0) { resultsList.add(listPerLevel); } return resultsList; } }