二叉树广度优先遍历

其实就是横着打印，一排一排的。通过队列实现。

• 模版

  public void LevelOrder()
        {
            Queue<Node> queue = new Queue<Node>();
            queue.Enqueue(_head);
            while (queue.Count>0)//队列中还有结点
            {
                Node node = (Node)queue.Dequeue();
                Console.Write(node);//打印结点
                if (node.Left != null) 
                {
                    queue.Enqueue(node.Left);
                }
                if (node.Right!=null)
                {
                    queue.Enqueue(node.Right);
                }
            }
        }

• 之字形打印二叉树

  public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        boolean reverse = false;
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        queue.add(pRoot);
        while(!queue.isEmpty()){
            ArrayList<Integer> list = new ArrayList<>();
            int c = queue.size();
            while(c-- > 0){
                TreeNode node = queue.poll();
                if(node == null){
                    continue;//空节点不加到list里面
                }
                list.add(node.val);
                queue.add(node.left);
                queue.add(node.right);
            }
                if(reverse){
                    Collections.reverse(list);
                }
               reverse = !reverse;
               if(list.size() != 0){
                   ret.add(list);
               }
            }
             return ret;
    }
  }

• 二叉树的右视图

  解析:打印每一行的最后一个

  /**
  * Definition for a binary tree node.
  * public class TreeNode {
  *     int val;
  *     TreeNode left;
  *     TreeNode right;
  *     TreeNode(int x) { val = x; }
  * }
  */
  class Solution {
     public List<Integer> rightSideView(TreeNode root) {
         if(root==null){
             return new ArrayList<>();
         }
         ArrayList<Integer> res = new ArrayList<>();
         Queue<TreeNode> queue = new LinkedList<>();
         queue.add(root);
         while(!queue.isEmpty()){
             int len= queue.size();
             for(int i=0;i<len;i++){ 
                 TreeNode node = queue.poll();
                 if(i==len-1){
                     res.add(node.val);
                 }
                 if(node.left != null){
                     queue.add(node.left);
                 }
                 if(node.right != null){
                     queue.add(node.right);
                 }
             } 
         }
         return res;
  }}