从上到下打印二叉树、按层打印二叉树-剑指offer

╰+哭是因爲堅強的太久メ 2021-12-11 00:21 301阅读 0赞

1.  **题目描述:**

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

**解题思路：**采取队列进行层次遍历。

1.  **题目描述：**

按层级把二叉树打印成多行。

**解决思路：**使用队列以及两个ArrayList来实现。

在剑指offer上面，题目结果必须完全一致

> 1.  import java.util.ArrayList;
> 2.  import java.util.Queue;
> 3.  import java.util.LinkedList;
> 4.  /\*\*
> 5.  public class TreeNode \{
> 6.      int val = 0;
> 7.      TreeNode left = null;
> 8.      TreeNode right = null;
> 9.      TreeNode root = null;
> 10.     public TreeNode(int val) \{
> 11.         this.val = val;
> 12.         this.left = left;
> 13.         this.right = right;
> 14.     \}
> 15.     public TreeNode()\{    
> 16.     \}
> 17. \}
> 18. \*\*/
> 19. public class Solution \{
> 20.     public ArrayList PrintFromTopToBottom(TreeNode root) \{
> 21.         ArrayList all = new ArrayList<ArrayList<Integer> >();
> 22.         Queue<TreeNode> que = new LinkedList<TreeNode>();
> 23.         que.add(root);
> 24.         while(!que.isEmpty())\{
> 25.             ArrayList<Integer> list = new ArrayList<Integer>();
> 26.             int cun = que.size();
> 27.             while(cun-- > 0)
> 28.             \{
> 29.             TreeNode t = que.poll();
> 30.              if(t==null)
> 31.                  continue;
> 32.               list.add(t.val);
> 33.               que.add(t.left);
> 34.               que.add(t.right);
> 35.             \}
> 36.             if(list.size() != 0)\{
> 37.                 for(int i=0;i<list.size();i++)
> 38.                 \{
> 39.                     all.add(list.get(i));
> 40.                 \}
> 41.             \}
> 42.                
> 43.         \}
> 44.         return all;
> 45.     \}
> 46. \}

下面是思路寻找的时候编辑的，参考使用

> 1.  package pratice618;
> 2.  import java.util.ArrayList;
> 3.  import java.util.LinkedList;
> 4.  import java.util.Queue;    
> 5.  public class printTree321\_711 \{
> 6.  //题目描述:从上往下打印出二叉树的每个节点，同层节点从左至右打印。
> 7.  //解题思路：采取队列进行层次遍历
> 8.      public static ArrayList<Integer> PrintFromTopToBottom(TreeNode root) \{
> 9.          Queue<TreeNode> queue = new LinkedList<TreeNode>();
> 10.         ArrayList<Integer> ret = new ArrayList<Integer>();
> 11.         queue.add(root);
> 12.         while (!queue.isEmpty()) \{
> 13.             int cnt = queue.size();
> 14.             System.out.println("cnt: "+cnt);
> 15.             while (cnt-- > 0) \{
> 16. //poll()方法获取，并删除队列的第一个元素或头部元素，删除了哈
> 17.                 TreeNode t = queue.poll();
> 18.                 if (t == null)
> 19.                     continue;
> 20.                 ret.add((Integer) t.data);
> 21.                 queue.add(t.left);
> 22.                 queue.add(t.right);
> 23.             \}
> 24.         \}
> 25.         return ret;
> 26.     \}
> 27. //题目描述：按层级把二叉树打印成多行
> 28. //解决思路：使用队列以及两个ArrayList来实现
> 29.     public static ArrayList<ArrayList<Integer>> PrintFromLevel(TreeNode root) \{
> 30.         Queue<TreeNode> queue = new LinkedList<TreeNode>();
> 31.         ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
> 32.         queue.add(root);
> 33.         while (!queue.isEmpty()) \{
> 34.             ArrayList<Integer> list = new ArrayList<Integer>();
> 35.             int cnt = queue.size();
> 36.             System.out.println("cnt: "+cnt);
> 37.             while (cnt-- > 0) \{
> 38. //poll()方法获取，并删除队列的第一个元素或头部元素
> 39.                 TreeNode t = queue.poll();
> 40.                 if (t == null)
> 41.                     continue;
> 42.                 list.add((Integer) t.data);
> 43.                 queue.add(t.left);
> 44.                 queue.add(t.right);
> 45.             \}
> 46.             if(list.size()!=0)\{
> 47.                 ret.add(list);
> 48.             \}
> 49.         \}
> 50.         return ret;
> 51.     \}
> 52.     public static void main(String\[\] args) \{
> 53.         TreeNode node = new TreeNode();        
> 54.         Object data\[\] = \{1,2,3,4,5,6,7\};
> 55.         node.creatTree(data);
> 56.         System.out.println("正常前遍历");
> 57.         node.preOrder(node.root);
> 58.         System.out.println(" ");
> 59.         
> 60.         System.out.println("从上到下打印： ");
> 61.         ArrayList<Integer> arry = PrintFromTopToBottom(node.root);
> 62.         for(int i=0;i<arry.size();i++)
> 63.         \{
> 64.             System.out.print(arry.get(i)+" ");
> 65.         \}
> 66.         System.out.println(" ");
> 67.          ArrayList<ArrayList<Integer>> arll= PrintFromLevel(node.root);
> 68.          for(int i=0;i<arll.size();i++)\{
> 69.              System.out.println(" "+arll.get(i));
> 70.          \}    
> 71.     \}
> 72. \}

### 二叉树的定义 ###

> 1.  package pratice618;
> 2.  import java.util.ArrayList;
> 3.  public class TreeNode \{
> 4.          public TreeNode left;
> 5.          public TreeNode right;
> 6.          public Integer val;
> 7.          public Object data;
> 8.          public TreeNode root;
> 9.          public TreeNode getLeft() \{
> 10.             return left;
> 11.         \}
> 12.         public void setLeft(TreeNode left) \{
> 13.             this.left = left;
> 14.         \}
> 15.         public TreeNode getRight() \{
> 16.             return right;
> 17.         \}
> 18.         public void setRight(TreeNode right) \{
> 19.             this.right = right;
> 20.         \}
> 21.         public Integer getVal() \{
> 22.             return val;
> 23.         \}
> 24.         public void setVal(Integer val) \{
> 25.             this.val = val;
> 26.         \}
> 27.         
> 28.         public TreeNode(Object data) \{
> 29.             super();
> 30.             this.data = data;
> 31.         \}
> 32.         public TreeNode(TreeNode left, TreeNode right, Integer val) \{
> 33.             super();
> 34.             this.left = left;
> 35.             this.right = right;
> 36.             this.val = val;
> 37.         \}
> 38.         public TreeNode()
> 39.         \{
> 40.             
> 41.         \}
> 42.         public TreeNode(TreeNode left, TreeNode right, Object data) \{
> 43.             super();
> 44.             this.left = left;
> 45.             this.right = right;
> 46.             this.data = data;
> 47.         \}
> 48.         public TreeNode(Object data\[\])\{//初始的左右孩子值为空
> 49.             this(null,null,data);
> 50.         \}
> 51.         public void creatTree(Object data\[\])\{
> 52.             ArrayList<TreeNode> dataTL = new ArrayList<TreeNode>();
> 53.             for(int i=0;i<data.length;i++)\{
> 54.                 dataTL.add(new TreeNode(data\[i\]));
> 55.             \}
> 56.             root = dataTL.get(0);//根节点为第一个节点
> 57.             for(int i=0;i<data.length/2;i++)
> 58.             \{
> 59.                 dataTL.get(i).left = dataTL.get(i\*2+1);
> 60.                 if(i\*2+2<dataTL.size())\{
> 61.                     dataTL.get(i).right = dataTL.get(i\*2+2);
> 62.                 \}
> 63.             \}
> 64.         \}
> 65.         public void preOrder(TreeNode root)\{//先序遍历二叉树
> 66.             if(root != null)\{
> 67.                 System.out.print(root.data+" ");
> 68.                 preOrder(root.left);
> 69.                 preOrder(root.right);
> 70.             \}
> 71.         \}
> 72.         public void inOrder(TreeNode root)\{//中序遍历二叉树
> 73.             if(root != null)\{
> 74.                 inOrder(root.left);
> 75.                 System.out.print(root.data+" ");                
> 76.                 inOrder(root.right);
> 77.             \}
> 78.         \}
> 79.         public void afterOrder(TreeNode root)\{//后序遍历二叉树
> 80.             if(root != null)\{
> 81.                 afterOrder(root.left);
> 82.                 afterOrder(root.right);
> 83.                 System.out.print(root.data+" ");                                                
> 84.             \}
> 85.         \}
> 86. \}

### **扫码关注一起随时随地学习！！！就在洋葱攻城狮，更多精彩，等你来！！** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70]: /images/20211210/75f3f035e6e8456ebb16ad88afb32a68.png