今天看了些二叉树的内容,想起四月份面试百度的时候被问到实现二叉树中的广度优先遍历,所以就尝试着用Java实现下,其实思想还是比较简单的。
算法相当于广度优先搜索,使用队列实现。队列初始化,将根节点压入队列。当队列不为空,进行如下操作:弹出一个节点,访问,若左子节点或右子节点不为空,将其压入队列。
这其中用到了队列,Java中LinkedList是一个非常标准的队列实现
- peek()方法,返回当前queue中的首元素但不删除该元素,如果队列为空则返回null。
- element()方法与peek()方法类似,但是当队列为空时抛出异常。
- poll()方法,返回并且删除queue中首元素,队列为空返回null。
- remove()方法与poll()方法类似,但当队列为空时抛出异常。
- add()与offer()方法都将再末尾添加一个元素。
这其中的方法名和一般数据结构书里的方法名不太一样,所以也得注意。
而且使用Queue<TreeNode> q = new LinkedList<>();
能够保证对象q中只有Queue中的方法,只是使用LinkedList实现罢了。
public static void LevelTraverse(TreeNode node){
if (node==null)
return;
Queue<TreeNode> q = new LinkedList<>();
q.add(node);
while (!q.isEmpty()){
TreeNode tmp = q.peek();
q.poll();
listLevel.add(tmp.value);
if (tmp.left!=null)
q.add(tmp.left);
if (tmp.right!=null)
q.add(tmp.right);
}
}