LinkedIn senior 电面

s442519769 发表于 2016-5-20 07:06
先求宽度 O（N）， 假设root 的x 值为0，
那求最左侧node的x值
有了最左侧的值，之后迭代x值，对每个no ...

感觉不太正确  你上代码看看

下个月 L家 店面！！ 楼主说的很详细！ 感谢

您好！
本帖隐藏的内容需要积分高于 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

请问楼主第二题的佛楼啊普中，打印时如何处理在某些层存在的某些节点占用同一个位置的重合问题呢（相邻两个父节点，左父的右儿子与右父的左儿子）？直观感觉多层以后相近的父节点位置整数除以二会因为进位而无法避免重合的冲突。

follow up 是间距输出应该怎样做呢？

思路跟把整个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. }

复制代码