2018-08-14 LeetCode在每个树行中找最大值

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
         List<Integer> ans = new LinkedList<>();
         if (root == null) {
            return ans;
        }
        queue.offer(root);
        TreeNode last = root;
        TreeNode nLast = null;
        int max = Integer.MIN_VALUE;
        while (!queue.isEmpty()) {
            root = queue.poll();
            max = root.val > max ? root.val : max;
            if (root.left != null) {
                queue.offer(root.left);
                nLast = root.left;
            }
            if (root.right != null) {
                queue.offer(root.right);
                nLast = root.right;
            }
            if (root == last && !queue.isEmpty()) {
                ans.add(max);
                max = Integer.MIN_VALUE;
                last = nLast;
            }
        }
        ans.add(max);
        return ans;
    }
}

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null) return res;
        queue.add(root);
        while (!queue.isEmpty()) {
            int max = Integer.MIN_VALUE;
            int size = queue.size();
            for ( int i = 0; i < size; i++) {
                TreeNode node = queue.remove();
                if (node.val > max) max = node.val;
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            res.add(max);
        }
        return res;
    }
}

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        check(root,0,list);
        return list;
    }

    public void check(TreeNode node,int index,List<Integer> list){
        if(node==null){
            return;
        }
        if(index >= list.size()){
            list.add(node.val);
        }else {
            list.set(index,Math.max(node.val,list.get(index)));
        }
        check(node.left,index+1,list);
        check(node.right,index+1,list);
    }
}