二叉树广度优先遍历（层次遍历）

宽度优先遍历，广度度优先遍历，层次遍历。 即从根节点开始依次遍历左子节点和右子节点，直到所有子节点都变遍历完为止。

遍历结果：{1,2,3,4,5,6,7,8,9,10 }

leetcode练习：

思路：

将树上顶点按照层次依次放入队列结构中，队列中元素满足 FIFO（先进先出）的原则。

初始化队列只包含一个节点 root 和层次编号 0 ： level = 0。

当队列非空的时候：          

    在输出结果 levels 中插入一个空列表，开始当前层的算法。        

     计算当前层有多少个元素：等于队列的长度。          

    将这些元素从队列中弹出，并加入 levels 当前层的空列表中。          

    将他们的孩子节点作为下一层压入队列中。        

     进入下一层 level++。

 public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> levels = new ArrayList<List<Integer>>();
    if (root == null) return levels;
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.add(root);
    int level = 0;
    while ( !queue.isEmpty() ) {
      levels.add(new ArrayList<Integer>());
      int level_length = queue.size();
      for(int i = 0; i < level_length; ++i) {
        TreeNode node = queue.remove();
        levels.get(level).add(node.val);
        if (node.left != null) queue.add(node.left);
        if (node.right != null) queue.add(node.right);
      }
      level++;
    }
    return levels;
  }

练习2：

思路：

宽度优先搜索顺序遍历每个节点的过程中，我们记录节点的位置信息 对于每一个深度（层次），第一个遇到的节点是最左边的节点，最后一个到达的节点是最右边的节点。（最左和最右的非空节点）

主要想法是给每个节点一个 position 值，如果我们走向左子树，那么 position -> position * 2，如果我们走向右子树，那么 position -> positon * 2 + 1。当我们在看同一层深度的位置值 L 和 R 的时候，宽度就是 R - L + 1。

public int widthOfBinaryTree(TreeNode root) {
        Queue<AnnotatedNode> queue = new LinkedList();
        queue.add(new AnnotatedNode(root, 0, 0));
        int curDepth = 0, left = 0, ans = 0;
        while (!queue.isEmpty()) {
            AnnotatedNode a = queue.poll(); //检索并删除此队列的头
            if (a.node != null) {
                queue.add(new AnnotatedNode(a.node.left, a.depth + 1, a.pos * 2));
                queue.add(new AnnotatedNode(a.node.right, a.depth + 1, a.pos * 2 + 1));
                if (curDepth != a.depth) { //层次变化一次，重新记录最左端位置
                    curDepth = a.depth;
                    left = a.pos;
                }
                ans = Math.max(ans, a.pos - left + 1);
            }
        }
        return ans;
    }


class AnnotatedNode {
    TreeNode node;
    int depth, pos;
    AnnotatedNode(TreeNode n, int d, int p) {
        node = n;
        depth = d;
        pos = p;
    }