LinkedIn senior 电面

LinkedIn 现在码农只招senior的了

电面第一题实现pow（a，b）
第二题tree level traversal， follow up 是带间距的输出
/**
*

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

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

     1
*        3   5
*      2   4   7
*    9   6   8

思路跟把整个binary tree inorder存到array里很像。
先dfs求树的高度h。
然后把每层都存到大小为2^h - 1的array里，逐层打出来就好了。

1. class Solution {
   
2. /**
   
3. * Sample input:
   
4. *
   
5. *          1
   
6. *         / \
   
7. *        2   3
   
8. *       / \  / \
   
9. *      4   5 6  7
   
10. *
    
11. * Expected output:
    
12. *    1
    
13. *    2 3
    
14. *    4 5 6 7
    
15. *
    
16. * Follow up expected output:
    
17. *      1   
    
18. *   2    3
    
19. * 4  5 6 7
    
20. **/
    
21.     public void levelOrderPrint(TreeNode root) {
    
22.         int h = dfs(root);
    
23.         int totalNodes = (1 << h) - 1;
    
24. 
    
25.         Map<TreeNode, int[]> m = new HashMap<>(); // node2(l,r)
    
26. 
    
27.         Queue<TreeNode> q = new LinkedList<>();
    
28.         q.offer(root);
    
29.         m.put(root, new int[]{0, totalNodes - 1});
    
30.         int currH = h;
    
31.         while (!q.isEmpty()) {
    
32.             int size = q.size();
    
33.             int[] lvl = new int[totalNodes];
    
34.             for (int i = 0; i < size; i++) {
    
35.                 TreeNode curr = q.poll();
    
36.                 int currPos = (m.get(curr)[1] + m.get(curr)[0]) / 2;
    
37.                 lvl[currPos] = curr.val;
    
38.                 if (curr.left != null) {
    
39.                     q.offer(curr.left);
    
40.                     m.put(curr.left, new int[]{m.get(curr)[0], currPos - 1});
    
41.                 }
    
42.                 if (curr.right != null) {
    
43.                     q.offer(curr.right);
    
44.                     m.put(curr.right, new int[]{currPos + 1, m.get(curr)[1]});
    
45.                 }
    
46.             }
    
47.             currH--;
    
48.             for (int i = 0; i < lvl.length; i++) {
    
49.                 System.out.print(lvl[i] != 0 ? lvl[i] : " ");
    
50.             }
    
51.             System.out.println();
    
52.         }
    
53.     }
    
54. 
    
55.     private int dfs(TreeNode root) {
    
56.         if (root == null) return 0;
    
57.         return Math.max(dfs(root.left), dfs(root.right)) + 1;
    
58.     }
    
59. 
    
60.     public static void main(String[] args) {
    
61.         TreeNode _1 = new TreeNode(1);
    
62.         TreeNode _2 = new TreeNode(2);
    
63.         TreeNode _3 = new TreeNode(3);
    
64.         _1.left = _2;
    
65.         _1.right = _3;
    
66.         TreeNode _4 = new TreeNode(4);
    
67.         TreeNode _5 = new TreeNode(5);
    
68.         _2.left = _4;
    
69.         _2.right = _5;
    
70.         TreeNode _6 = new TreeNode(6);
    
71.         TreeNode _7 = new TreeNode(7);
    
72.         _3.left = _6;
    
73.         _3.right = _7;
    
74.         new Solution().levelOrderPrint(_1);
    
75.     }
    
76. 
    
77. }

复制代码

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

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

follow up  啥思路呢

follow up可以用vertical traversal 来解决 楼主怎么做的

为啥只要senior

我的思路：
1 求出树的高度 h 用一个2的h次方的数组存取每一层的结果
2。第一层的存取位置 curpos = 2 的 h-1次方
3， 接下来循环每一层  如果 node.left != null  pos =   curpos /2
     node.right !=null  pos =  curpos+ curpos/2;

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

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

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

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

求出共有几层，比如Ｎ层，打印的时候，每层依次空Ｎ个格，Ｎ－1个格，Ｎ－2, Ｎ－3.。。。。。。

我想问你pass了吗？