题目:从上往下打印二叉树
描述:从上往下打印出二叉树的每个节点,同层节点从左至右打印。
思路: 使用一个队列进行辅助操作,对二叉树进行广度优先遍历,把二叉树的数据元素压入队列,先从根节点开始遍历所有元素,然后将根节点加入队伍中,访问过程中,先访问根节点,再访问它的左右孩子节点,循环遍历。本题中,输入{5,4,#,3,#,2,#,1},对应二叉树如图所示:
首先将根节点加入队列中,
遍历二叉树,在5之后发现它的左孩子4,将4加入队列中,
本题中,所有节点右孩子都是空,则后面节点同4,继续遍历节点,
最后1节点没有孩子节点,结束遍历,出队列,返回{5,4,3,2,1}。
Java程序如下所示:
import java.util.ArrayList; /** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) { //创建一个队列存储节点 ArrayList<Integer> list=new ArrayList<>(); ArrayList<TreeNode>queue=new ArrayList<>(); if(root==null) return list; queue.add(root);//遍历二叉树,根节点加入队列 while(!queue.isEmpty()) { TreeNode node= queue.remove(0); if(node.left!=null) queue.add(node.left); if(node.right!=null) { queue.add(node.right); } list.add(node.val); } return list; } }
时间复杂度:对二叉树进行广度优先遍历,时间复杂度为0(N)。