FB Phone Screen 9/1

就问了一道题BST Two Sum。 先用InOrder加HashSet解决。O(n) time and O(n

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

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

从大到小，然后就和sorted array解法一样了。

here is the code for two Iterator, Time O(n), Space O(h) as next() need stack:

1. /**
   
2. * Definition for a binary tree node.
   
3. * public class TreeNode {
   
4. *     int val;
   
5. *     TreeNode left;
   
6. *     TreeNode right;
   
7. *     TreeNode(int x) { val = x; }
   
8. * }
   
9. */
   
10. class Solution {
    
11.     public boolean findTarget(TreeNode root, int k) {
    
12.         // Time O(n), Space O(h)
    
13.         if (root == null)
    
14.             return false;
    
15.         
    
16.         LeftIterator leftIterator = new LeftIterator(root);
    
17.         RightIterator rightIterator = new RightIterator(root);
    
18.         int left = leftIterator.next();
    
19.         int right = rightIterator.next();
    
20.         
    
21.         while (left < right) {
    
22.             int twoSum = left + right;
    
23.             if (twoSum == k) {
    
24.                 return true;
    
25.             }
    
26.             if (twoSum < k && leftIterator.hasNext()) {
    
27.                 left = leftIterator.next();
    
28.             } else if (twoSum < k && !leftIterator.hasNext()) {
    
29.                 break;
    
30.             }
    
31.             if (twoSum > k && rightIterator.hasNext()) {
    
32.                 right = rightIterator.next();
    
33.             } else if (twoSum > k && rightIterator.hasNext()) {
    
34.                 break;
    
35.             }
    
36.         }
    
37.         return false;
    
38.     }
    
39.         
    
40.     class LeftIterator {
    
41.         Stack<TreeNode> stack;
    
42. 
    
43.         LeftIterator(TreeNode root) {
    
44.                 stack = new Stack<TreeNode>();
    
45.                 while (root != null) {
    
46.                         stack.push(root);
    
47.                         root = root.left;
    
48.                 }
    
49.         }
    
50. 
    
51.         boolean hasNext() {
    
52.                 return !stack.isEmpty();
    
53.         }
    
54. 
    
55.         int next() {
    
56.                 TreeNode node = stack.pop();
    
57.                 int result = node.val;
    
58.                 if (node.right != null) {
    
59.                         node = node.right;
    
60.                         while (node != null) {
    
61.                                 stack.push(node);
    
62.                                 node = node.left;
    
63.                         }
    
64.                 }
    
65.                 return result;
    
66.         }   
    
67.     }
    
68.    
    
69.     class RightIterator {
    
70.         Stack<TreeNode> stack;
    
71. 
    
72.         public RightIterator(TreeNode root) {
    
73.                 stack = new Stack<TreeNode>();
    
74.                 while (root != null) {
    
75.                         stack.push(root);
    
76.                         root = root.right;
    
77.                 }
    
78.         }
    
79. 
    
80.         public boolean hasNext() {
    
81.                 return !stack.isEmpty();
    
82.         }
    
83. 
    
84.         public int next() {
    
85.                 TreeNode node = stack.pop();
    
86.                 int result = node.val;
    
87.                 if (node.left != null) {
    
88.                         node = node.left;
    
89.                         while (node != null) {
    
90.                                 stack.push(node);
    
91.                                 node = node.right;
    
92.                         }
    
93.                 }
    
94.                 return result;
    
95.         }      
    
96. }
    
97.    
    
98.     }

复制代码

补充内容 (2017-10-2 18:21):
reference: https://www.programcreek.com/201 ... tree-iterator-java/

vbnmmnbv 发表于 2017-9-6 23:34
直接traverse bst, 然后binary search另一个node不就可以节省空间了吗

那样时间是n/2*logn 也就是nlogn 不是n

ilovestat 发表于 2017-9-3 02:32
如何理解  用了两个 BST Iterator 就优化空间了？

同问啊。两个iterator怎么就节省空间了

谢谢楼主分享
写两种iterator这个想法确实很不错

牛！
谢谢楼主分享。。。。电话面是，是codepad写题目，自己跑test cases吗？

怎么理解用了两个bst iterator 就优化空间了？

如何理解  用了两个 BST Iterator 就优化空间了？

用codepad写，不用跑test case。Iterator空间是O(logN).

xyz1995 发表于 2017-9-6 12:57
同问啊。两个iterator怎么就节省空间了

NVM. The space cost of a stack is O(lgn). 打扰了

其实可以优化到 O(1)空间，两个 iterator 用 morris traversal 实现就行。面试的时间可以提一下

直接traverse bst, 然后binary search另一个node不就可以节省空间了吗