谷歌fulltime phone screen面筋，已跪

请问 insert方法是指什么意思？谢谢1

jjustc 发表于 2016-6-16 04:52
请问 insert方法是指什么意思？谢谢1

就是问你怎么维护链表的顺序。。。

来贴个代码，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. }

复制代码

lz咋不准备一下再面呢

chaosMonkey 发表于 2016-11-14 18:05
lz咋不准备一下再面呢

在准备，谷歌冷冻期一年

jyttwc901231 发表于 2016-6-16 05:23
就是问你怎么维护链表的顺序。。。

请问是利用insert的方法给链表排序吗

chaosMonkey 发表于 2016-12-11 11:10
请问是利用insert的方法给链表排序吗

是让你实现树的insert方法，然后要让List继续是inorder

jyttwc901231 发表于 2016-12-11 11:13
是让你实现树的insert方法，然后要让List继续是inorder

谢谢lz回复  那这就是往BST里面插入一个node的意思吧，同时要维护list顺序

chaosMonkey 发表于 2016-12-11 11:31
谢谢lz回复  那这就是往BST里面插入一个node的意思吧，同时要维护list顺序

是，就是这个意思。。。