FB Uday onsite

wey46 发表于 2018-10-3 00:23
我也在想，莫不是用个Queue模拟一下stack？会不会有点投机取巧

threaded tree O（1）space 不过感觉有点扯淡吧问这个。

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

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

suomobai0 发表于 2018-10-3 00:20
谢谢楼主 祝楼主顺利拿到offer~

谢谢～～～～～～

wey46 发表于 2018-10-3 00:23
我也在想，莫不是用个Queue模拟一下stack？会不会有点投机取巧

不用stack的意思就是觉得说不想用太多的space，你用queue的话其实和原来没差别呀

lyyy7537721825 发表于 2018-10-3 00:44
threaded tree O（1）space 不过感觉有点扯淡吧问这个。

我觉得应该不是考虑这些……

楼主不是说有个parent 指针吗？

walffy 发表于 2018-10-3 07:59
不知道你有没有看懂呢，就是Node不只有left， next和value，还有parent，指向上一级。我就是设了一个glob ...

然后呢？我觉得遍历左子树后到root不好做啊

yb819342347 发表于 2018-10-3 11:54
然后呢？我觉得遍历左子树后到root不好做啊

我设了prev，存上一次的那个node，判断一下cur.left==prev？就好了吧

第二题的follow up 可以参考这个帖： http://www.1point3acres.com/bbs/thread-142642-1-1.html

第二题follow up写了下解法：

1. class BSTIteratorN(object):
   
2.     def __init__(self, root):
   
3.         """
   
4.         :type root: TreeNode
   
5.         """
   
6.         self.prev = None
   
7.         self.cur = root
   
8.         while self.cur and self.cur.left:
   
9.             self.cur = self.cur.left
   
10. 
    
11.     def hasNext(self):
    
12.         """
    
13.         :rtype: bool
    
14.         """
    
15.         return self.cur != None
    
16. 
    
17.     def next(self):
    
18.         """
    
19.         :rtype: int
    
20.         """
    
21.         node = self.cur
    
22.         if self.prev == None:
    
23.             self.cur = self.cur.parent
    
24.         else:
    
25.             if self.prev == self.cur.parent:
    
26.                 self.cur = self.cur.parent.parent
    
27.             elif self.prev != self.cur.right:
    
28.                 self.cur = self.cur.right
    
29.                 while self.cur and self.cur.left:
    
30.                     self.cur = self.cur.left
    
31.         self.prev = node
    
32.         return node.val
    

复制代码