按之字打印二叉树-剑指Offer-Java

╰半橙微兮° 2021-12-11 02:39 231阅读 0赞

**题目描述：**

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

> 1.  import java.util.ArrayList;
> 2.  import java.util.Stack;
> 3.  /\*
> 4.  public class TreeNode \{
> 5.      int val = 0;
> 6.      TreeNode left = null;
> 7.      TreeNode right = null;
> 8.      public TreeNode(int val) \{
> 9.          this.val = val;
> 10.     \}
> 11. \}
> 12. \*/
> 13. public class Solution \{
> 14.     public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) \{
> 15.         ArrayList<ArrayList<Integer> > all = new ArrayList<ArrayList<Integer> >();
> 16.         Stack<TreeNode> stack1 = new Stack<TreeNode>();
> 17.         int level = 1;
> 18.         stack1.push(pRoot);
> 19.         Stack<TreeNode> stack2 = new Stack<TreeNode>();
> 20.         while(!stack1.isEmpty() || !stack2.isEmpty())\{           
> 21.             if(level%2 != 0)\{
> 22.                 ArrayList<Integer> list = new ArrayList<Integer>();
> 23.                 while(!stack1.empty())\{
> 24.                     TreeNode t = stack1.pop();
> 25.                     if(t != null)\{
> 26.                         list.add(t.val);                       
> 27.                         stack2.push(t.left);
> 28.                         stack2.push(t.right);
> 29.                     \}
> 30.                  \}
> 31.                     if(!list.isEmpty())\{
> 32.                         all.add(list);
> 33.                         level++;
> 34.                     \}
> 35.             \} else\{
> 36.                 ArrayList<Integer> list = new ArrayList<Integer>();
> 37.                 while(!stack2.empty())\{
> 38.                     TreeNode t = stack2.pop();
> 39.                     if(t != null)\{
> 40.                         list.add(t.val);
> 41.                         stack1.push(t.right);
> 42.                         stack1.push(t.left);
> 43.                     \}
> 44.                   \}
> 45.                     if(list.size()>0)\{
> 46.                         all.add(list);
> 47.                         level++;
> 48.                     \}
> 49.             \}
> 50.         \}
> 51.         return all;
> 52.     \}
> 53. \}

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

![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/b43e2889d0714c21bb0c6f9fc0bf98b2.png