FB家电面面经

morris in-order traversal

稍微想了一下，感觉题目对两个BST的intersection不清楚，如果intersection是指子树（包括结构上）完全相同的话，前面层住说的先flatten为linkedlist然后找list的intersection的方法是不对的。eg:
   2                 2
     \                 \
      5                 4
   /   \                  \
4      6                 5
                             \
                              6
我认为constant space的方法是morris traversal 找到相同的node，再对比两个node的子树相同。求拍

有parent的话用中序遍历从两个tree的最小节点开始比，然后依次找下个节点就可以了吧

这题要求不能用递归？

感觉是写BST的inorder iterator.
这样就变成intersection of two sequences了.

efny 发表于 2014-5-10 05:16
挂了，应该是个华裔哥。我一开始说了2种有extra space的方法，他不让我写，问我有没有不需要extra space的 ...

这个面试官简直脑残啊。。。。应该告诉他“you need some education..”

sj1456 发表于 2014-5-19 11:31
stack不是extra space？？？。。。另外O（1）space是不是就是没用extra space？

O(1)是常量空间啊，和in-place不一样的

neusharon 发表于 2014-11-30 03:24
稍微想了一下，感觉题目对两个BST的intersection不清楚，如果intersection是指子树（包括结构上）完全相同 ...

是的，flatten成list的方法需要考虑还原成之前的树， 因为按理说应该不允许毁坏之前的数据结构，除非是有明确要求可以改变这棵树。而且保存遍历结果的list需要extra space的，不合题意啊。

如果是比较子树结构相等，为何要是BST呢，一般的Binary Tree就行啊。总觉得这个面试官自己都不清楚

楼上有人说对了，就是iterator的变型嘛。。虽然面试官可能表述不清楚。但是不用递归是肯定的，也不能把全部节点都保存出来，这样耗费O(n)的复杂度。
1、因为是BST，所以迅速想到中序遍历是有序的，所以可以从两个树分别各自最左边开始比较。那么就是implement 一个 BST的iterator。
2、鉴于面试官说可以用栈，那么这个题目的额外空间复杂度应该是O(h)是树的高度。

3、如果不想用栈，可以利用parent节点，实现和栈一样的功能。

4、楼主已经说了，是找到同时出现的数啊，所以不是指结构上的交叉。

所以本题考察：中序遍历的非递归实现 + find intersection of two array 如果基础扎实10min应该可以码完。
同样出现的facebook面试为：here 以及 there
以下贴出代码：（用stack，O(h)额外空间）

1. public class BSTIterator {
   
2.     private Stack<TreeNode> stack = new Stack<TreeNode>();
   
3.    
   
4.     public BSTIterator(TreeNode root) {
   
5.         pushAllLeft(root);  
   
6.     }
   
7. 
   
8.     /** @return whether we have a next smallest number */
   
9.     public boolean hasNext() {
   
10.         return !stack.empty();
    
11.     }
    
12. 
    
13.     /** @return the next smallest number */
    
14.     public int next() {
    
15.         TreeNode node = stack.pop();
    
16.         pushAllLeft(node.right);
    
17.         
    
18.         return node.val;
    
19.     }
    
20.    
    
21.     public int min() {
    
22.         if (!stack.empty()) {
    
23.             return stack.peek();
    
24.         }
    
25.     }
    
26.    
    
27.     private void pushAllLeft(TreeNode root) {
    
28.         TreeNode head = root;
    
29.         while (head != null) {
    
30.             stack.push(head);
    
31.             head = head.left;
    
32.         }
    
33.     }
    
34. }
    
35. 
    
36. public class Solution {
    
37.     public ArrayList<TreeNode> findIntersectionInTwoBST
    
38.       (TreeNode rootA, TreeNode rootB) {
    
39.         if (rootA == null || rootB == null) {
    
40.             return null;
    
41.         }
    
42.         BSTIterator ia = new BSTIterator(rootA);
    
43.         BSTIterator ib = new BSTIterator(rootB);
    
44.         ArrayList<TreeNode> ans = new ArrayList<TreeNode>();
    
45.         while (ia.hasNext() && ib.hasNext()) {
    
46.             if (ia.min().val == ib.min().val) {
    
47.                 ans.add(ia.next());
    
48.             } else if (ia.min().val < ib.min().val) {
    
49.                 ia.next();
    
50.             } else {
    
51.                 ib.next();
    
52.             }
    
53.         }
    
54.         
    
55.         return ans;
    
56.     }
    
57. }

复制代码

CrossTheWall 发表于 2015-1-31 02:40
是的，flatten成list的方法需要考虑还原成之前的树， 因为按理说应该不允许毁坏之前的数据结构，除非是有 ...

不是指结构上的交叉。。我个人感觉是iterator而已 所以上面贴了下代码。、，，