Linkedin二面面经

NANA1123 发表于 2014-10-20 01:24
N是给定的，我补充了文字说明你可以看看

那感觉level order traversal一下？要是出现N叉树不满的情况怎么办呢。。。

billupus 发表于 2014-10-20 06:08
那感觉level order traversal一下？要是出现N叉树不满的情况怎么办呢。。。

应该是BFS，允许有一个节点不满N

kinslover 发表于 2014-10-20 01:07
题里说了，只有一个点可以是例外，其儿子数目介于0到N之间。所以我觉得跑一遍BFS把新树尽量堆满就行了… ...

哦 谢谢 不好意思 我没仔细看lz的说明 谢谢提醒

NANA1123 发表于 2014-10-20 01:22
可以有一个exception

哦 明白了 谢谢 那这道题就是bfs 然后顺次把每个节点填满 就觉得够了 谢谢lz的解释

csgtc 发表于 2014-10-17 08:19
就用BFS走一下咯，copy过去的tree也用一个queue存，满了就dequeue这样，这题应该不难吧

大牛还是如此关注各种新鲜面经 lol

需要两个队列，一个队列用来存等待设置N节点的节点，另一个队列保存bfs的结果。每次从bfs的队列里面poll出peek，需要做三件事情，一个是将它设置为第一个队列peek的儿子，另外一个是将它的儿子放在bfs的队列中，第三个是将它放在第一个队列中等待设置Nchild。需要给第一个对列的peek设置一个count， 记录它已经设置了多少儿子。每次到了N以后出队，count归0。这题是很绕，祝楼主好运！

赞面经。第二题，可以把所有的节点先放到一个数组里面。然后把这些点连成一个N叉树。连起来的时候需要注意，因为你可以连成一个完全树，所以A[i]的N个儿子分别是i*N+1到i*N+N。这样一个个连起来就好了，连起来很方便。所以就是1.按level 遍历存到数组里面，preorder应该也可以。这样保证不违反那个sibling的条件。2.在数组里面连出一个full N tree. 主要考察的是遍历和完全树的trick

如果实在要优化的话，可以把数组变成一个queue。然后用按level遍历。如果把A[i]和N个儿子连起来之后，可以从队列里面pop出A[i]。只是一点小优化而已。

一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖！被警告三次，系统会自动封杀ID！

想支持楼主，请点击帖子下方的"好苗""分享""收藏"键，酌情给楼主加大米（系统不扣你自己的分）。
积分不够看不了帖子，请参考论坛导航里的"帮助"，"新手提纲"里有攒积分指南

1. public class CompactTreeBuilder {
   
2. 
   
3.     public static TreeNode compact(TreeNode root, int n) {
   
4.         if (root == null || n == 0) return root;
   
5.         Queue<TreeNode> q1 = new LinkedList<TreeNode>();
   
6.         Queue<TreeNode> q2 = new LinkedList<TreeNode>();
   
7.         q1.offer(root);
   
8.         q2.offer(root);
   
9.         int currLevel = 1, nextLevel = 0;
   
10.         while (!q1.isEmpty()) {
    
11.             TreeNode front = q1.poll();
    
12.             for (TreeNode child : front.children) {
    
13.                 q1.offer(child);
    
14.                 q2.offer(child);
    
15.                 nextLevel++;
    
16.             }
    
17.             if (--currLevel == 0) {
    
18.                 currLevel = nextLevel;
    
19.                 nextLevel = 0;
    
20.             }
    
21.         }
    
22.         TreeNode newRoot = q2.poll();
    
23.         fillChildren(newRoot, q2, n);
    
24.         return newRoot;
    
25.     }
    
26.    
    
27.     private static void fillChildren(TreeNode root, Queue<TreeNode> queue, int n) {
    
28.         if (root == null || queue.isEmpty()) return;
    
29.         int count = 0;
    
30.         root.children = new ArrayList<TreeNode>();
    
31.         while (!queue.isEmpty() && count < n) {
    
32.             root.children.add(queue.poll());
    
33.             count++;
    
34.         }
    
35.         for (TreeNode child : root.children) {
    
36.             fillChildren(child, queue, n);
    
37.         }
    
38.     }
    
39. }
    
40. 
    
41. class TreeNode {
    
42.     int value;
    
43.     List<TreeNode> children;
    
44.     public TreeNode(int vlaue) {
    
45.         this.value = value;
    
46.         children = new ArrayList<TreeNode>();
    
47.     }
    
48. }

复制代码

csgtc 发表于 2014-10-17 08:19
就用BFS走一下咯，copy过去的tree也用一个queue存，满了就dequeue这样，这题应该不难吧

我觉得如果是从没见过的新题，median难度的题就可以花上30-45分钟了。然而见过的median难度的题基本能10分钟内敲定。。。。