试题
考点

数据结构-二叉树-二叉树遍历

面5笔5

如何实现二叉树层次遍历?

前往“校招VIP”小程序,刷题更快
最新校招难题刷题,快来进刷题群吧
解答

与树的前中后序遍历的DFS思想不同,层次遍历用到的是BFS思想。一般DFS用递归去实现(也可以用栈实现),BFS需要用队列去实现。
层次遍历的步骤是:
1.对于不为空的结点,先把该结点加入到队列中
2.从队中拿出结点,如果该结点的左右结点不为空,就分别把左右结点加入到队列中
3.重复以上操作直到队列为空

public static void levelOrder(TreeNode biTree)
{//层次遍历
if(biTree == null)
return;
LinkedList<TreeNode> list = new LinkedList<TreeNode>();
list.add(biTree);
TreeNode currentNode;
while(!list.isEmpty())
{
currentNode = list.poll();
System.out.println(currentNode.value);
if(currentNode.left != null)
list.add(currentNode.left);
if(currentNode.right != null)
list.add(currentNode.right);
}
}


评论
暂无评论

加载更多