剑指OfferJZ59：按之字形顺序打印二叉树-java版

傷城~ 2022-10-16 06:04 76阅读 0赞

### 剑指OfferJZ59：按之字形顺序打印二叉树-java版 ###

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

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70]

之字形打印：即第一行（奇数行）从左往右打印，第二行（偶数行）从右往左打印，第三行从左往右打印。。。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70 1]

打印时把每一层当成一个数组

dfs深度优先搜索：（比如：二叉树中的前序遍历，中序遍历，后序遍历）dfs是按递归来实现的，它优先搜索深度，再回溯，优先访问的是没有访问过的子节点，使用栈实现

**bfs宽度优先搜索**：bfs是按一层一层来访问的，bfs优先访问的是兄弟节点，只有这一层全部访问完才能访问下一层，使用**队列**实现

该题使用的是bfs宽搜：  
首先队列中初始位置为1（首先队列中初始位置放入当前节点（也就是根节点））

**第一次迭代**：将1取出并删除（queue.poll() 从队列头部取出再删除一个元素），并把1的值放入到准备的数组中，这时队列是空的，然后先将1的左孩子2放入队列，再将1的右孩子3放入队列  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70 2]

**第二次迭代**：将2取出并删除，并把2的值放入到准备的数组中，然后同上将先后将2的左右孩子4和5放入队列  
**第三次迭代**：将3取出并删除，并把3的值放入到准备的数组中，由于3的左右孩子为空，这里不做操作  
**第四次迭代**：将4取出并删除，并把4的值放入到准备的数组中，由于4的左右孩子为空，这里不做操作  
**第五次迭代**：将5取出并删除，并把5的值放入到准备的数组中，由于5的左右孩子为空，这里不做操作  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70 3]

这道题还要考虑一个重要的问题：  
此题不是单纯的把所有节点当成一个数组打印出来  
而是**把每一层当成一个数组**打印（难点）  
这就要求我们在遍历的过程中判断当前节点是否是当前层的最后一个节点  
通过一个变量标记当前层的节点有没有被遍历完，判断当前层是第几层

import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.Queue;
    
    /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */
    public class Solution { 
        public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) { 
            //大数组
            ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
            //宽搜bfs：使用队列
            Queue<TreeNode> queue=new LinkedList<>();
            //首先队列中初始位置放入当前节点（也就是根节点）
            queue.add(pRoot);
            int sum=1;//用来保存每一层的节点个数
            int num=1;//用来判断当前层是第几层
    
            while(!queue.isEmpty() && pRoot!=null){ 
                //准备一个数组（存储每一层节点的小数组）
                ArrayList<Integer> list = new ArrayList<>();
                int temp=0;//用来统计每一层节点个数
                while(sum>0){ 
                    //将当前节点取出并删除
                    TreeNode node=queue.poll();
                    assert node!=null;
                    //并把当前节点的值放入到准备的数组中
                    list.add(node.val);
    
                    if(node.left!=null){ 
                        temp++;
                        queue.add(node.left);//将左孩子放入队列
                    }
                    if(node.right!=null){ 
                        temp++;
                        queue.add(node.right);//将右孩子放入队列
                    }
                    sum--;
                }
                sum=temp;
                if(num%2==0){ 
                    //（偶数层）从右往左打印
                    for(int i=0,j=list.size()-1;i<j;i++,j--){ 
                        //将第i个位置和第j个位置的数字交换（将list数组反置）
                        int res=list.get(i);
                        list.set(i, list.get(j));
                        list.set(j,res);
                    }
                }
                num++;
                //
                ans.add(list);//将小数组放入大数组中
            }
            return ans;
        }
    }

![在这里插入图片描述][20210527102925729.gif_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70]: /images/20221014/9c549aca333a4b169117542a9d255420.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70 1]: /images/20221014/1205c605c2b449bd89ed00cc087ca4ee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70 2]: /images/20221014/cf2e7fef2ac240848c489bb8e022f322.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70 3]: /images/20221014/8ecc7dfba097437e86a16a7f0dafaa02.png
[20210527102925729.gif_pic_center]: /images/20221014/3997ed91c525477c9c5c0fa7cef7b4f1.png