FB 8/19 面经

两轮design， 两轮 coding
design 答得不好， 问得很细，

coding 有一轮不好：

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式

terative 。 时间不够了。。。

有什么比较好的办法 ？

minggr 发表于 2016-10-10 01:51
Iteration如下，就是post-order traversal的iterative版本

贴个自己的code.用的是level traversal,找出最深层的head和tail节点，用一个map来track 节点到父节点的映射。
如果head 和tail相等，说明最深层就一个节点，如果不等，分别从map里向parent节点搜索，知道发现一个公共的节点即为LCA。
public int lcaBFS(TreeNode root) {
                if(root == null)        return -1;
                // <node -> parent node>
                Map<TreeNode, TreeNode> map = new HashMap<TreeNode, TreeNode>();

                TreeNode head = null, tail = null;        // the head and tail node in a level
                Queue<TreeNode> que = new LinkedList<TreeNode>();
                que.offer(root);
                map.put(root, null);
                while(!que.isEmpty()) {
                        head = null; tail = null;
                        int sz = que.size();
                        while(sz-- > 0) {
                                TreeNode curr = que.poll();
                                if(head == null)        head = curr;
                                if(sz == 0)        tail = curr;
                                if(curr.left != null) {
                                        map.put(curr.left, curr);
                                        que.offer(curr.left);
                                }
                                if(curr.right != null) {
                                        map.put(curr.right, curr);
                                        que.offer(curr.right);
                                }
                        }
                }

                while(head != tail){
                        head = map.get(head);
                        tail = map.get(tail);
                }
                return head.val;
        }

recursive 直接DFS找最底层最左和最右边的点然后求这两个点的LCA即可，iteration就变成BFS找最后一层的第一个和最后一个，找出点后求LCA即可

最近这个题很高频啊，其实dfs遍历，返回的时候返回lca和depth，每个node如果有大于一个子节点的depth相同就返回这个node，如果有一个子节点depth更深就返回个子节点lca，这个o(n)就可以了

能说说design的题目吗

有一个比较naive的想法，先BFS（同时用map存节点映射到父节点）到最后一层，然后从最后一层开始往上找父节点直到只有一个父节点。

iterative感觉可以用一个HashMap 得到最深节点到根节点的路径。然后K个最深节点求交点。

hychin 发表于 2016-8-19 12:16
recursive 直接DFS找最底层最左和最右边的点然后求这两个点的LCA即可，iteration就变成BFS找最后一层的第一 ...

理论上是这样，
每一层记录一个leftmost， 一个 rightmost， 如果没有下层了， 再从 root 找 path ？
感觉应该有更好办法 。

DFS的话，最直接的办法还是iterative  post order traversal用hashmap存每个child node的深度和candidate。 hashmap可以变走边删除 space 也能做到O(h)  time 还是O(N)

BFS也可以 level order traversal 每个node 都带一个path info  比如向左是0  向右是1  最后一层的所有node的共同前缀就是lca 第一个例子 最后一层5 、6 就是010 011  共同前缀是01  也就是 3那个node 第二个例子最后一层是4 5 6  就是000 010 011  共同前缀是0  就是root 1 node

我的想法是： BFS，保存每一层的queue，queue的节点中保存该节点父亲节点在上一层中的位置。遍历完之后，对最后一个队列的头尾俩节点同时向上搜索父亲，直到父亲相同。有点绕，不知到说清楚没有

为啥我觉得题目不太看得懂。如果只有一个节点深度3， 一个节点深度2，返回谁的LCA？如果一个深度3，两个深度2，返回哪两个的LCA

cacofish 发表于 2016-8-20 04:35
为啥我觉得题目不太看得懂。如果只有一个节点深度3， 一个节点深度2，返回谁的LCA？如果一个深度3，两个深 ...

返回深度3节点本身