谷歌fulltime phone screen面筋，已跪

recruitor email找到我。问我有没有兴趣面谷歌。由于Lz自己确实在准备跳槽。只是没准备好。于是想面一个试试。
电话接通

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

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

空间复杂度。
第一次面试太紧张，已跪。
祝大家早日找到工作。

来贴个代码，java的，stack实现

1. public class InorderNext {
   
2. 
   
3.         public static void main(String[] args) {
   
4.                 TreeNode root=new TreeNode(20);
   
5.                 TreeNode r1=new TreeNode(10);
   
6.                 TreeNode r2=new TreeNode(30);
   
7.                 root.left=r1;root.right=r2;
   
8.                 TreeNode r3=new TreeNode(5);
   
9.                 TreeNode r4=new TreeNode(15);
   
10.                  r1.left=r3;r1.right=r4;
    
11.                 TreeNode r5=new TreeNode(12);
    
12.                 TreeNode r6=new TreeNode(17);
    
13.                 r4.left=r5;r4.right=r6;
    
14.                 TreeNode r7=new TreeNode(16);
    
15.                 r6.left=r7;
    
16.                 InorderNext i=new InorderNext();
    
17.                 i.next(root);
    
18.                 TreeNode tmp=r3;
    
19.                 while(tmp!=null){
    
20.                         System.out.print(tmp.val+",");
    
21.                         tmp=tmp.next;
    
22.                 }
    
23.                
    
24.         }
    
25.        
    
26.         private void next(TreeNode r){
    
27.                 Stack<TreeNode> stack=new Stack<>();
    
28.                 while(r!=null){
    
29.                         stack.push(r);
    
30.                         r=r.left;
    
31.                 }
    
32.                
    
33.                 while(!stack.isEmpty()){
    
34.                         TreeNode p=stack.pop();
    
35.                         if(p.right!=null){
    
36.                                 TreeNode right=p.right;
    
37.                                 while(right!=null){
    
38.                                         stack.push(right);
    
39.                                         right=right.left;
    
40.                                 }
    
41.                         }
    
42.                         if(stack.isEmpty()){
    
43.                                 p.next=null;
    
44.                                 return;
    
45.                         }
    
46.                         p.next=stack.peek();
    
47.                 }
    
48.         }
    
49. 
    
50. }
    
51. 
    
52. class TreeNode{
    
53.         int val;
    
54.         TreeNode left;
    
55.         TreeNode right;
    
56.         TreeNode next;
    
57.         public TreeNode(int v){
    
58.                 this.val=v;
    
59.                 this.left=null;
    
60.                 this.right=null;
    
61.                 this.next=null;
    
62.         }
    
63. }

复制代码

recursion写起来不是更简洁吗？

1. void convert(TreeNode* n, TreeNode* &last){
   
2.    
   
3.    
   
4.     if(n) {
   
5.         
   
6.         convert(n->left, last);
   
7.         
   
8.         if(last){
   
9.             last->next = n;
   
10.             n->prev = last;
    
11.         }
    
12.         
    
13.         last = n;
    
14.         
    
15.         convert(n->right, last);
    
16.     }
    
17. }

复制代码

这个用stack inorder 比较好写

blackrose 发表于 2016-6-9 04:36
这个用stack inorder 比较好写

嗯，我挂了电话就想起来stack好写。。。。打电话的时候太紧张。。什么都想不起来。。。。

blackrose 发表于 2016-6-9 04:36
这个用stack inorder 比较好写

感觉你是大神啊。。。所有题目都能看见你快速解答。。

yueliu2366 发表于 2016-6-9 04:40
感觉你是大神啊。。。所有题目都能看见你快速解答。。

快下班了。才有空刷一下论坛。。。

楼主的follow up 是insert一个BST node 吗

Recursion不太好搞，只能用Stack了

handsomecool 发表于 2016-6-9 05:21
recursion写起来不是更简洁吗？

嗯，我觉得这样也行。。。。

wzy0791 发表于 2016-6-9 05:21
Recursion不太好搞，只能用Stack了

recursion其实也行，见楼上