FB intern Round1

想问问lz第二题的binary tree是full tree还是any tree啊？ any tree的话代码也不好写的

yuxrose 发表于 2015-4-5 04:31
想问问lz第二题的binary tree是full tree还是any tree啊？ any tree的话代码也不好写的

好像没有什么区别吧 只要是前序遍历就可以吧？

strstr 能用brute force 吗

ppips 发表于 2015-4-5 04:38
好像没有什么区别吧 只要是前序遍历就可以吧？

不太一样吧，如果是full tree的话，left child直接连right child, 如果不是的话，像下面这个
     A
B         C
D null  E null

这种情况D是连E，还是不连，保持原状？ 连E的话就得找下个同level的下个child，这里比较麻烦一下，也是我觉得next pointer II 比 I 最麻烦的地方。

汗我好像看错题了，不是要connect nodes，是successor啊！

lch04 发表于 2015-4-5 00:52
第二题还是LC原题吖

能告诉我是哪道题吗？

yuxrose 发表于 2015-4-5 07:10
能告诉我是哪道题吗？

lc原题是inorder iterator 这个是preorder 不过差不多实现起来

请问有大神贴一下tree iterator 的代码吗？烧香感谢。。。

表示我二面的时候也遇到了差不多的面试官。。是个棒子。。爱理不理的。。LZ后来有结果了吗？

haungge0385 发表于 2015-4-6 16:13
请问有大神贴一下tree iterator 的代码吗？烧香感谢。。。

请指正

1. // Tree iterator (preorder)
   
2. public static class BSTIterator {
   
3.         TreeNode next;
   
4.         Stack<TreeNode> stack;
   
5.         public BSTIterator(TreeNode root) {
   
6.                 next = root;
   
7.                 stack = new Stack<TreeNode>();
   
8.                 if (next != null)
   
9.                         stack.push(next);
   
10.                 next = stack.isEmpty() ? null : stack.pop();
    
11.         }
    
12. 
    
13.         /** [url=home.php?mod=space&uid=160137]@return[/url] whether we have a next smallest number */
    
14.         public boolean hasNext() {
    
15.                 return next != null;
    
16.         }
    
17. 
    
18.         /** @return the next smallest number */
    
19.         public int next() {
    
20.                 int res = next.val;
    
21.                 if (next != null) {
    
22.                         TreeNode n = next;
    
23.                         if (n.right != null)
    
24.                                 stack.push(n.right);
    
25.                         if (n.left != null)
    
26.                                 stack.push(n.left);
    
27.                 }
    
28.                 next = stack.isEmpty() ? null : stack.pop();
    
29.                 return res;
    
30.         }
    
31. }

复制代码