FB Phone Screen 9/1

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

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

楼主behavior问了什么呀？

Phone interview 没问bq

楼主被要求写优化后的代码了吗，还是就说说思路就可以？

从大到小的iterator怎么实现啊？也是用stack么？没思路啊。。。

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/

jiahuanghuijun 发表于 2017-10-2 16:34
从大到小的iterator怎么实现啊？也是用stack么？没思路啊。。。

I pasted code for you.

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

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