剑指offer（二十二）从上往下打印二叉树（Java版）

　　描述
　　从上往下打印出二叉树的每个节点，同层节点从左至右打印。 示例1
　　输入：{5,4,#,3,#,2,#,1}
　　返回值：  [5,4,3,2,1]
　　第一种解法，使用一个队列来做完辅助工具，由于队列的特性的先进先出，第一次就把根节点放进去，然后循环遍历左右节点，依次放入队列中，最后依次从队列中取出节点，放入list中即可，代码如下public static ArrayList firstPrintFromTopToBottom(TreeNode root) {         ArrayList list = new ArrayList<>();         if(null == root){             return list;         }         Queue queue = new LinkedList<>();         queue.offer(root);         while (!queue.isEmpty()){             TreeNode poll = queue.poll();             list.add(poll.val);             if(null != poll.left){                 queue.offer(poll.left);             }             if(null != poll.right){                 queue.offer(poll.right);             }         }         return list;     }
　　第二种解法，先计算出树的最大深度，然后依次循环遍历即可,代码如下public static ArrayList secondPrintFromTopToBottom(TreeNode root) {         ArrayList list = new ArrayList<>();         if(null == root){             return list;         }         int depth = depth(root);         for (int i = 0; i < depth; i++) {             foreachTree(root,i,list);         }          return list;     }      public static void foreachTree(TreeNode root,int level,ArrayList list){         if(null == root){             return;         }         if(level == 0){             list.add(root.val);         }         foreachTree(root.left,level-1, list);         foreachTree(root.right,level-1, list);     }      /**      * 求树的最大深度      * @param root      * @return      */     public static int depth(TreeNode root){         if(null == root){             return  0;         }         int l = depth(root.left);         int r = depth(root.right);         if(l > r){             return l + 1;         }else {             return r + 1;         }     }
　　完整代码如下public class MainPrintFromTopToBottom {      public static void main(String[] args) {         //根节点-->10         TreeNode treeNode1 = new TreeNode(10);          //左孩子-->9         TreeNode treeNode2 = new TreeNode(9);          //右孩子-->20         TreeNode treeNode3 = new TreeNode(20);          //20的左孩子-->15         TreeNode treeNode4 = new TreeNode(15);          //20的右孩子-->35         TreeNode treeNode5 = new TreeNode(35);         //根节点的左右孩子         treeNode1.setLeft(treeNode2);         treeNode1.setRight(treeNode3);          //20节点的左右孩子         treeNode3.setLeft(treeNode4);         treeNode3.setRight(treeNode5);          ArrayList integers = secondPrintFromTopToBottom(treeNode1);         System.out.println(＂integers = ＂ + integers);     }      public static ArrayList firstPrintFromTopToBottom(TreeNode root) {         ArrayList list = new ArrayList<>();         if(null == root){             return list;         }         Queue queue = new LinkedList<>();         queue.offer(root);         while (!queue.isEmpty()){             TreeNode poll = queue.poll();             list.add(poll.val);             if(null != poll.left){                 queue.offer(poll.left);             }             if(null != poll.right){                 queue.offer(poll.right);             }         }         return list;     }       public static ArrayList secondPrintFromTopToBottom(TreeNode root) {         ArrayList list = new ArrayList<>();         if(null == root){             return list;         }         int depth = depth(root);         for (int i = 0; i < depth; i++) {             foreachTree(root,i,list);         }          return list;     }      public static void foreachTree(TreeNode root,int level,ArrayList list){         if(null == root){             return;         }         if(level == 0){             list.add(root.val);         }         foreachTree(root.left,level-1, list);         foreachTree(root.right,level-1, list);     }      /**      * 求树的最大深度      * @param root      * @return      */     public static int depth(TreeNode root){         if(null == root){             return  0;         }         int l = depth(root.left);         int r = depth(root.right);         if(l > r){             return l + 1;         }else {             return r + 1;         }     } }