前一段时间找人内推了微软苏州，职位是 Microsoft search team的 software engineer。 面试之前听说微软会狂怼算法， 然而平常算法刷的不多，所以花了几天时间临时抱佛脚突击刷了一些常见的算法（内心OS： 巨硬应该不会按照常规套路出招）。

面试用的是 M 家自带的 Microsoft team， 体验倒没有网上说的那么不堪， 感觉良好。面试官好像不是这个team 的， 但是说话很亲和， 也比较好沟通。上来先自我介绍了下， 然后就是问项目， 时间差不多了， 开始了写题时间。 开了一个共享的一个online编辑器 http://collabedit.com。emmm， 其实就是个白板。

第一题： 给一棵二叉树， 和一个 target（二叉树某节点）， 找出所有与target距离为 k 的节点的值的集合。

这道题，我一开始居然卡住了，因为找距离为 k 的点的话需要往很多方向去找，还要处理 k 值过大的问题（不存在与target 距离 为 k 的点），而二叉树的节点只有指向左节点和右节点的两个指针， 如果还有个 parent 指针的话应该可以解决问题。和面试官确认了下确实节点只有两个指针（太紧张了没想到自己遍历的时候保存每个节点的父指针）。后来面试官提示了下，突然恍然大悟， 给出了自己的一个思路：

先遍历二叉树所有节点， 用 hashMap 存储每个节点和父亲节点的映射， 这样的话这棵二叉树可以看作一个无向图， 我可以往每个节点的任意一个方向走。 我们把 target节点当成起点， 借助队列向周围三个方向做 BFS， 找到所有距离为 k 的点的集合，过程中用一个 哈希表标记节点是否被访问过，防止走回头路。以下直接附上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    HashMap<TreeNode, TreeNode> map = new HashMap<>();
    Set<TreeNode> isVisited = new HashSet<>();

    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
        List<Integer> results = new ArrayList<>();
        if (root == null || target == null) {
            return results;
        }
        int res = 0;
        traversal(root);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(target);

        while (!queue.isEmpty()) {
            int qSize = queue.size();
            if (res == K) {
                for (int i = 0; i < qSize; i++) {
                    int val = queue.poll().val;
                    results.add(val);
                }
                return results;
            } 

            for (int i = 0; i < qSize; i++) {
                TreeNode cur = queue.poll();
                isVisited.add(cur);
                if (cur.left != null && !isVisited.contains(cur.left)) {
                    queue.add(cur.left);
                }
                if (cur.right != null && !isVisited.contains(cur.right)) {
                    queue.add(cur.right);
                }
                if (map.get(cur) != null && !isVisited.contains(map.get(cur))) {
                    queue.add(map.get(cur));
                }
            }
            res++;
        }
        return results;
    }

    private void traversal(TreeNode node) {
        if (node == null) {
            return;
        }

        if (node.left != null) {
            map.put(node.left, node);
        }

        if (node.right != null) {
            map.put(node.right, node);
        }

        traversal(node.left);
        traversal(node.right);
    }
}

目前只是第一轮的 onsite， 如果有第二轮的话会在下面继续更新。