剑指OfferJZ22：从上往下打印二叉树-java版

ゞ浴缸里的玫瑰 2023-01-23 05:55 134阅读 0赞

### 剑指OfferJZ22：从上往下打印二叉树-java版 ###

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

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

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

**深搜（dfs）**  
深搜，看名字就知道到是优先往深处找，不撞南墙终不悔。深搜，像是一个人走迷宫，遇见岔路不知道怎么走，就瞎选一个（程序中一搬从头遍历），走到底，不对，回到岔路口，选另一条路，接着走。

深搜的实现一般用栈或递归，不断深入。

**宽搜（bfs）**  
宽搜全名宽度搜索，就是放宽了搜，就像是雷达那样，中间一个点不断放出电磁波，一圈一圈往外扩散，很容易就能发现目标，而且发现了必然就是最近的（最优解）。

宽搜的实现一般使用队列，不断扩散。

根据题意可知**使用宽搜**方法

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

public class jz22 { 
        public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) { 
    
            ArrayList<Integer> ans = new ArrayList<>();
            Queue<TreeNode> queue = new LinkedList<>();//放入遍历二叉树的节点（本质上是维护宽搜的）
            if(root!=null){ 
                queue.add(root);
            }
            //迭代的过程-->宽搜
            while(!queue.isEmpty()){ 
                TreeNode node=queue.peek();//peek()返回队列的头元素，不删除
                ans.add(node.val);//将当前节点的val值放入ArrayList中
                //同层节点从左至右打印
                if(node.left!=null){ 
                    queue.add(node.left);
                }
                if(node.right!=null){ 
                    queue.add(node.right);
                }
                queue.poll();//poll()返回队列的头元素，并删除；当前节点val值已经放入ans中，所以要删去
            }
            return ans;
        }
    }

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70]: /images/20221004/25da3589ef1742aeb5ebeaf7214fc9ed.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70 1]: /images/20221004/171d609488de4e64bfe71a77fe057cfc.png
[20210713103232891.gif_pic_center]: /images/20221004/672cb078172643cc95fc9ee56fd9dec2.png