BFS 入门(1)

最简单的例子，树的层次遍历

 原始树的前序字符串“9!5!4!#!#!6!#!#!3!#!#!”
public static void hieraTravTreeNode(TreeNode head){
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(head); // 起点，最初始值入队列
        while(!queue.isEmpty()){ // 判断队列是否为空
          TreeNode node =  queue.poll(); //队列不为空，则弹出队首元素
          System.out.print(node.val+" ");
          //尝试扩展队列！！
          if(node .left != null){
              queue.add(node.left);
          }
          if(node.right != null){
              queue.add(node.right);
          }
        }
    }
## 结果：9 5 3 4 6
//这例子中没有考虑到结点的 “判重” “记录步数”，“前驱结点（最短路径）的问题”！！！故是最简单的BFS.

// 进阶，记录层次的 树的层次遍历。
 public static void hieraTravTreeNode2(TreeNode head) {
        int level2 = 0;// 记录层次的
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(head);
        while (!queue.isEmpty()) {
            level2 ++;
            System.out.print("level "+ level2+" :");
            int size = queue.size(); // 这一层有多少个数据
            //// 对于这一层数据进行遍历
            for(int i=0; i<size;i++){
                TreeNode node = queue.poll();
                System.out.print(node.val+" ");
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            System.out.println();
        }
    }
## 结果：
level 1 :9 
level 2 :5 3 
level 3 :4 6 
// 保存树的结构与数组中

public static ArrayList<ArrayList<Integer>> hieraTravTreeNode3(TreeNode head) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
          // 用来保存树中所有的数据
        ArrayList<ArrayList<Integer>> treeList = new ArrayList<ArrayList<Integer>>();
        queue.add(head);
        while (!queue.isEmpty()) {
            // 用来保存每一层的元素！！
            ArrayList<Integer> list = new ArrayList<Integer>();
            int size = queue.size(); // 这一层有多少个数据
            // 对于这一层数据进行遍历
            for(int i=0; i<size;i++){
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            treeList.add(list);  // 将这一层加入到 整体中
        }
        // 这只是
        for(int i = 0;i<treeList.size();i++){
            int level = i+1;
            ArrayList<Integer> li = treeList.get(i);// 每一层的
            System.out.print("level "+level+" : ");
            for(int j=0; j< li.size();j++){
                System.out.print(li.get(j)+" ");
            }
            System.out.println();
        }
        return treeList;
    }
##例子：

1.     3
2. / \
3. 9 20
4. / \
5. 15 7

层次遍历的结果List为： [   [3],   [9,20],   [15,7] ]                                                                                                                                       

   https://blog.csdn.net/chenchaofuck1/article/details/51277653 
   https://www.cnblogs.com/theskulls/p/5125858.html