您需要在二叉树的每一行中找到最大的值。

示例：

输入: 

          1
         / \
        3   2
       / \   \  
      5   3   9 

输出: [1, 3, 9]

 

 

思路：

层序遍历的思想  在同一层找最大的

    public List<Integer> largestValues(TreeNode root) {
	  List<Integer> res = new ArrayList<Integer>();    
	  if (root==null) return res;  
	    Queue<TreeNode> queue = new LinkedList<TreeNode>();
	    queue.add(root);
	       
	    while(queue.size() != 0){
	       int size = queue.size();       //每层的数目量
	       int max = Integer.MIN_VALUE;   //用于保存每层的最大值
	       for(int i = 0; i < size; i++){
	            TreeNode cur = queue.poll();
	            max=Math.max(cur.val, max);
	            if(cur.left!= null)queue.add(cur.left);
	            if(cur.right!=null)queue.add(cur.right);
	          }
	       res.add(max);
	     }	
	 return res;
	}