Facebook 二面面经

楼主是实习电面咯？

wingman989898 发表于 2016-2-18 07:48
楼主是实习电面咯？

是的~两轮实习电面...

YJ_Li 发表于 2016-2-18 07:25
电面的时候能查leetcode 或在网上找其他资料吗？

可以呢，反正对方也不知道。。

raccoon 发表于 2016-2-18 08:03
可以呢，反正对方也不知道。。

这个没有 detector 或 用 webcam 检查行动吗

感觉这道题很好用dfs啊，先dfs到最下面，所以每个节点返回的是当前下面最深的子节点的深度，以及这些最深的子节点汇聚在哪个节点。比如说，原题假设a上面还有parent的话，a向上返回的就是节点b和depth 5(因为假设a上面还有一层)。如果一个节点收到两个子节点返回的这个信息，就可以唯一的确定应该怎么返回给更高的一层。

我也写了一写，dfs with hash map

        public TreeNode minSubtreeDeepestLeaf(TreeNode root) {
                // record the deepest depth under each node in a map
                // for a parent, if left and right subtree have the same
                // deepest depth, return the parent node itself,
                // otherwise, return the subtree with deepest child
                if (root == null) {
                        return root;
                }
                Map<TreeNode, Integer> map = new HashMap<>();
                return helper(root, map, 1);
        }

        private TreeNode helper(TreeNode root, Map<TreeNode, Integer> map, int depth) {
                if (root.left == null && root.right == null) {
                        map.put(root, depth);
                        return root;
                }
                if (root.left == null) {
                        return helper(root.right, map, depth + 1);
                }
                if (root.right == null) {
                        return helper(root.left, map, depth + 1);
                }
                TreeNode leftResult = helper(root.left, map, depth + 1);
                TreeNode rightResult = helper(root.right, map, depth + 1);
                if (map.get(leftResult) == map.get(rightResult)) {
                        map.put(root, map.get(leftResult));
                        return root;
                }
                return map.get(leftResult) > map.get(rightResult) ? leftResult : rightResult;
        }

感谢楼主分享经验！