Sort binary tree by levels（4Kyu） - 图1

题目

You are given a binary tree:

  1. public class Node {
  2.   public Node left;
  3.   public Node right;
  4.   public int value;
  5.   public Node(Node l, Node r, int v) {
  6.     left = l;
  7.     right = r;
  8.     value = v;
  9.   }
  10. }

Your task is to return the list with elements from tree sorted by levels, which means the root element goes first, then root children (from left to right) are second and third, and so on. Return empty list is root is ‘null’. 您的任务是返回包含按级别排序的树中元素的列表，这意味着根元素排在第一位，然后根子元素（从左到右）排在第二位和第三位，依此类推开始。根为”null”,返回空列表.

例子

  1.              2
  2.         8        9               -->   [2,8,9,1,3,4,5]
  3.       1  3     4   5
  5.              1
  6.         8        4              -->  [1,8,4,3,5,7]
  7.           3         5
  8.                        7

原题链接

分析

对二叉树按层级进行遍历，使用BFS广度优先遍历，非常经典。

我的解法

  1. import java.util.*;
  3. class Kata {
  4.   public static List<Integer> treeByLevels(Node node)
  5.   {
  6.     Queue<Node> queue = new LinkedList<>();
  7.     List<Integer> list = new ArrayList<>();
  8.     if (node != null) {
  9.       queue.add(node);
  10.     }
  11.     while (!queue.isEmpty()){
  12.         Node peek = queue.poll();
  13.         list.add(peek.value);
  14.         if (peek.left != null){
  15.             queue.add(peek.left);
  16.         }
  17.         if (peek.right != null){
  18.             queue.add(peek.right);
  19.         }
  20.     }
  21.     return list;
  22.   }
  23. }

参考解法

  1. import java.util.*;
  3. class Kata {  
  5.   public static List<Integer> treeByLevels(Node node)
  6.   {
  7.     if (node == null) return Collections.emptyList();    
  8.     List<Integer> res = new ArrayList<>();    
  10.     //breadth-first search
  11.     Queue<Node> nodesToVisit = new ArrayDeque(); //ArrayDeque is better than LinkedList if no removing in between is involved
  12.     nodesToVisit.offer(node);
  14.     Node current;
  15.     while ((current = nodesToVisit.poll()) != null) {
  16.       res.add(current.value);
  17.       if (current.left != null) nodesToVisit.offer(current.left);
  18.       if (current.right != null) nodesToVisit.offer(current.right);
  19.     }  
  21.     return res;
  22.   }
  23. }

提升

  1. java中queue方法

    boolean add(E e) //将指定的元素插入此队列（如果立即可行且不会违反容量限制），在成功时返回 true，如果当前没有可用的空间，则抛出 IllegalStateException。 E element() //获取，但是不移除此队列的头。 boolean offer(E e) //将指定的元素插入此队列（如果立即可行且不会违反容量限制），当使用有容量限制的队列时，此方法通常要优于 add(E)，后者可能无法插入元素，而只是抛出一个异常。 E peek() //获取但不移除此队列的头；如果此队列为空，则返回 null。 E poll() //获取并移除此队列的头，如果此队列为空，则返回 null。

E remove() //获取并移除此队列的头。

  1. 没有中间结点删除的情况下，ArrayDeque比LinkedList性能要好。
  2. 队列中添加node时，offer优于add,删除node时，poll优于remove。
  3. bfs伪代码如下
    1. void bfs(起始状态){
    2.  queue<element_type> qu;//创建队列
    3.  qu.push(起始状态入队)；
    4.  while(!qu.empty()){//当队列非空
    5.      if(当前状态x方向可走)
    6.          qu.push(当前状态+x);//该状态入队
    7.      if(当前状态向y方向可走)
    8.          qu.push(当前状态+y);//该状态入队
    9.      …………………
    10.      处理(队顶)qu.top();
    11.      相应操作；
    12.      qu.pop();//队首弹出队
    13.  }//一次循环结束，执行下一次循环
    14. }

    参考资料

    DFS与BFS——理解简单搜索(中文伪代码+例题)