美团面试题分享

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

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

输入:

 1         / \
 2        3   2
 3       / \   \  
 4      5   3   9
 5
 6```java
 7
 8输出: [1, 3, 9]
 9
10LeetCode原题，题号是515。
11
12先说答案：
13
14```cs
15/**
16 * Definition for a binary tree node.
17 * public class TreeNode {
18 *     int val;
19 *     TreeNode left;
20 *     TreeNode right;
21 *     TreeNode(int x) { val = x; }
22 * }
23 */
24class Solution {
25    public List<Integer> largestValues(TreeNode root) {
26
27        List<Integer> res  =new ArrayList<>();
28
29        Queue<TreeNode>  q = new LinkedList<>();
30
31        if (root ==null ){
32            return res;
33        }
34        q.add(root);
35
36        while(!q.isEmpty()){
37
38            int size = q.size();
39
40            int max = Integer.MIN_VALUE;
41
42            for(int i = 0; i<size; i++){
43
44               TreeNode node = q.poll();
45               max = Math.max(max,node.val);
46
47               if (node.left !=null){
48                   q.add(node.left);
49               }
50
51               if (node.right !=null){
52                   q.add(node.right);
53               }
54
55            }
56
57            res.add(max);
58        }        
59        return res;
60    }
61
62}

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

2 手写 hashmap的put方法

我不知道多少人能写出来，说实话直到现在我也写不出来。但冷静下来细想，人家真的是考你能不能完全写出来吗？我想，可能还是考查你对于put的熟悉程序，对流程的把握，如果你把基本流程用伪代码讲清楚了，怎么也能答到及格吧。有关这个问题的解读可以看小盒子之前的文章：

一次性搞定HashMap面试

关注公众号获取更多精彩内容