题目描述:
标签:树 广度优先搜索 二叉树
从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。
代码:
思路分析:层序遍历的思想
1、首先最重要的是使用队列+广度优先搜索来实现层序遍历操作。
2、把根节点加入队列,对应此时的层数。以此时队列的长度为循环终止条件开始循环:取队列节点的值加入当层的list,并把该节点的左右节点加入队列。其实每层即对应一次大循环此时队列里的节点个数。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int[] levelOrder(TreeNode root) { if(root == null){ return new int[0]; } List<Integer> list = new ArrayList<>(); Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while(!queue.isEmpty()){ int level = queue.size(); for(int i = 0;i < level;i++){ TreeNode node = queue.poll(); list.add(node.val); if(node.left != null){ queue.add(node.left); } if(node.right != null){ queue.add(node.right); } } } int[] ans = new int[list.size()]; int cnt = 0; for(int num : list){ ans[cnt++] = num; } return ans; } }