脸书电面

脸书 电面：

1. 利口 舅二姨
2. 二叉树 中序 i

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

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

不可只写不说。

求大米！

感觉第二道题，如果用O(N) 或者O(H)的空间去存储数的话，BST和普通BT是没啥区别的。如果只能利用O(1)空间的，BST可以获得O(N * H)的算法复杂度，非BST将是O(N^2)的复杂度。

moluren 发表于 2019-3-2 18:07
感觉第二道题，如果用O(N) 或者O(H)的空间去存储数的话，BST和普通BT是没啥区别的。如果只能利用O(1)空间的 ...

能否详细解释一下O(1) space 的 BST  iterator 思路？没有想到：（
多谢大神！

ColorLessZ 发表于 2019-3-3 08:12
能否详细解释一下O(1) space 的 BST  iterator 思路？没有想到：（
多谢大神！

这个是我之前写的代码，还可以优化一下的。请参考，如有错误不负任何责任。

1. public class BSTIterator {
   
2.     private TreeNode root, current;
   
3. 
   
4.     /*
   
5.      * @param root: The root of binary tree.
   
6.      */
   
7.     public BSTIterator(TreeNode root) {
   
8.         if (root == null) return;
   
9.         this.root = root;
   
10. 
    
11.         current = root;
    
12.         while (current.left != null) current = current.left;
    
13.     }
    
14. 
    
15.     /*
    
16.      * @return: True if there has next node, or false
    
17.      */
    
18.     public boolean hasNext() {
    
19.         return current != null;
    
20.     }
    
21. 
    
22.     /*
    
23.      * @return: return next node
    
24.      */
    
25.     public TreeNode next() {
    
26.         TreeNode next = current;
    
27.         current = successor(current);
    
28.         return next;
    
29.     }
    
30. 
    
31.     private TreeNode successor(TreeNode node) {
    
32.         TreeNode successor = null, p = root;
    
33.         while (p != null) {
    
34.             if (p.val == node.val) break;
    
35.             if (node.val > p.val) p = p.right;
    
36.             else {
    
37.                 successor = p;
    
38.                 p = p.left;
    
39.             }
    
40.         }
    
41. 
    
42.         if (p == null) return null;
    
43.         if (p.right == null) return successor;
    
44. 
    
45.         p = p.right;
    
46.         while (p.left != null) p = p.left;
    
47.         return p;
    
48.     }
    
49. }

复制代码

补充内容 (2019-3-3 12:28):
或许用Morris算法实现也可以，不过没这么做过。

moluren 发表于 2019-3-3 12:25
这个是我之前写的代码，还可以优化一下的。请参考，如有错误不负任何责任。

[mw_shl_code=java,true]p ...

Oops! 我题目写错了.....抱歉， 问的是pre-order......

ColorLessZ 发表于 2019-3-3 13:25
Oops! 我题目写错了.....抱歉， 问的是pre-order......

那就不知道考的是BST的啥了。

Lz几年经验了