美团面试题分享-阿里云开发者社区

美团面试题分享

2022-04-23 138

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 利用队列做BFS，有关二叉树层次遍历的思路都可以套用。

以下两道题是本人几年前面试遇到过的真实面试题，由于当年刷题不够，思路也不到位，导致没有答好。今天正好刷LeetCode，看到原题了，勾起了我的回忆......

1 给定一棵二叉树，找到每一行中的最大值。

输入:

输出: [1, 3, 9]

LeetCode原题，题号是515。

先说答案：

/**
 * 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> largestValues(TreeNode root) {
        List<Integer> res  =new ArrayList<>();
        Queue<TreeNode>  q = new LinkedList<>();
        if (root ==null ){
            return res;
        }
        q.add(root);
        while(!q.isEmpty()){
            int size = q.size();
            int max = Integer.MIN_VALUE;
            for(int i = 0; i<size; i++){
               TreeNode node = q.poll();
               max = Math.max(max,node.val);
               if (node.left !=null){
                   q.add(node.left);
               }
               if (node.right !=null){
                   q.add(node.right);
               }
            }
            res.add(max);
        }        
        return res;
    }
}