FB 8/19 面经

ksc_ 发表于 2016-10-10 02:03
确实遍历的方法不好想，求问设计题细节

@ksc_ 你中毒了吗……

感觉这题挺难的，不容易啊，加油楼主！！！

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;
        }

zzh730 发表于 2016-8-23 06:19
是的，题里是多叉树，稍稍改下就好了

题目不是写着 binary tree么

Lilian1109 发表于 2016-8-23 03:16
这个貌似get到了， 贴一个我的代码， 是这么个意思吗？

代码不对吧。。。 [21,null,3,null, 4] 这个例子。
base case 有点小问题？