二叉树的宽度优先遍历：按层的遍历方式，请你用队列实现DFS，或者请你用栈实现BFS

提示：之前的什么先序，中序，后序遍历都是深度优先的方式，俗称DFS
之前的什么先序，中序，后序遍历都是深度优先的方式，俗称DFS遍历
（1）二叉树，二叉树的归先序遍历，中序遍历，后序遍历，递归和非递归实现
重要的基础知识：
（2）请你用栈实现队列，即用数据结构【栈】来设计数据结构【队列】
（3）请你用队列实现栈，即用数据结构【队列】来实现数据结构【栈】

今天来说说按层的遍历方式，也即二叉树的宽度优先遍历

文章目录

• 二叉树的宽度优先遍历：按层的遍历方式，请你用队列实现DFS，或者请你用栈实现BFS
• • @[TOC](文章目录)
• 题目
• 一、审题
• 二、解题
• 请你用队列实现DFS，或者请你用栈实现BFS
• 总结

题目

请你按照层打印二叉树

一、审题

示例：1 2 3 4 5 6 7

本题二叉树的节点和树为：

public static class Node{
        public int value;
        public Node left;
        public Node right;
        public Node(int v){
            value = v;
        }
    }

    //构造一颗树，今后方便使用
    public static Node generateBinaryTree(){
        //树长啥样呢
        //          1
        //        2   3
        //       4 5 6 7
        Node head = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        head.left = n2;
        head.right = n3;
        Node n4 = new Node(4);
        Node n5 = new Node(5);
        n2.left = n4;
        n2.right = n5;
        Node n6 = new Node(6);
        Node n7 = new Node(7);
        n3.left = n6;
        n3.right = n7;
        return head;
    }

二、解题

反正打印一个x节点，然后自己的兄弟节点，因为x和自己的兄弟节点时同一层，从左往右，按层打印。
然后下一次，就应该打印x的左右子，以及x的兄弟节点的左右子，因为这些节点，又是同一层。

这个机制如何实现？
之前我们说DFS是通过栈来实现的
现在我没说BFS是通过队列实现的

这样做，最开始将head加入队列
开始循环操作：弹出打印。
然后看其左右子是否不为null，是就加入队列，否则不管。

每一次打印一个cur时，它左右子就得依次进队列，当当前层都打印完了，队列就会依次把下一层都打印出来。

（1）最开始加入头节点head=1；然后开始循环操作：
（2）cur=1弹出，打印1；看看其左右子，不空加入队列：23依次入队列
（3）cur=2弹出，打印2；看看其左右子，不空加入队列：45依次入队列
（4）cur=3弹出，打印3；看看其左右子，不空加入队列：67依次入队列
（5）cur=4弹出，打印4；看看其左右子，空
（6）cur=5弹出，打印5；看看其左右子，空
（7）cur=6弹出，打印6；看看其左右子，空
（8）cur=7弹出，打印7；看看其左右子，空

宽度优先遍历就是这么回事，
手撕一波代码：

//复习：这样做，最开始将head加入队列
    //开始循环操作：弹出打印。
    //	然后看其左右子是否不为null，是就加入队列，否则不管。
    public static void bfsBinaryTreePrint(Node head){
        if (head == null) return;

        LinkedList<Node> queue = new LinkedList<>();
        queue.add(head);
        while (!queue.isEmpty()){
            Node cur = queue.poll();
            System.out.print(cur.value + " ");

            //按层加入左右子
            if (cur.left != null) queue.add(cur.left);
            if (cur.right != null) queue.add(cur.right);
        }
        //图也是这么干BFS，DFS就是用栈，一条道走到黑
    }

    public static void test(){
        Node cur = generateBinaryTree();
        BreadthFirstSearch(cur);
        bfsBinaryTreePrint(cur);
    }

    public static void main(String[] args){
        test();
    }

非常简单的，比非递归实现DFS简单的多了

1 2 3 4 5 6 7 
1 2 3 4 5 6 7 

请你用队列实现DFS，或者请你用栈实现BFS

将来在图的操作中，也是类似的

图也会有DFS和BFS
DFS就是一条道走到黑，用栈不断往里压入，每次都把一个节点cur一条路径不断地操作下去，再回来操作cur的另一条路径
DFS是用栈来实现的。之前说那些非递归方法实现二叉树的先序，中序，后序遍历都是DFS。
（1）二叉树，二叉树的归先序遍历，中序遍历，后序遍历，递归和非递归实现

BFS就是很宽地散开，用队列一次性压入周围所有节点，把cur邻居全部压入，然后再操作下一层。
本文就是用队列实现的BFS，机制上面已经说了。


那么未来，有的面试官可能会问，请你用队列实现DFS，或者请你用栈实现BFS
看清这个字眼！！！【正常情况下，用栈实现DFS，用队列实现BFS，现在让你反着来实现，你怎么做？】
怎么搞呢？
你别被吓唬了

之前咱们说过，用栈可以实现队列，用队列可以实现栈
——我们只能用栈实现DFS，如果非要用队列来实现DFS，那只能先用队列实现栈，再用你这个栈，去实现DFS。
——同样：我们只能用队列实现BFS，如果非要用栈来实现BFS，那只能先用栈实现队列，再用你这个队列实现BFS。

懂了我的意思了吧？下面这俩文章好好学习：
（1）请你用栈实现队列，即用数据结构【栈】来设计数据结构【队列】
（2）请你用队列实现栈，即用数据结构【队列】来实现数据结构【栈】

总结

提示：重要经验：

1）二叉树的深度优先遍历DFS用栈来实现，或者递归直接简单地实现，二叉树的宽度优先遍历BFS用队列实现，这和图一样。
2）请你用队列实现DFS，或者请你用栈实现BFS，考的是让你用队列实现栈的能力，用栈实现队列的能力。
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。