实现Queue接口的LinkedList类

今天看了些二叉树的内容,想起四月份面试百度的时候被问到实现二叉树中的广度优先遍历,所以就尝试着用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);
}
}

×

纯属好玩

扫码支持
扫码打赏,你说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦

文章目录
,