讨论一到Indeed 面经高频题 Tree to array

马上要去onsite了，看了一道Indeed 的高频面经：
Store a binary tree to array, 怎么存节省空间？

我的理解是如果只寸binary tree的话，一个TreeNode 要存一个value, 已经两个pointer to l

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

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

不知道还有没有其他更好的方法？
另外我把用 heap 表示 binary tree的答案写出来。不知道对不对？

1. import java.util.*;
   
2. 
   
3. public class Solution {
   
4.     private Queue<TreeNode> nodeQueue = new LinkedList<>();
   
5.     private Queue<Integer> indexQueue = new LinkedList<>();
   
6.     public Integer[] compressTree(TreeNode root) {
   
7.         // step 1: get the height of the tree
   
8.         int height = getTreeHeight(root);
   
9.         int n = (int) Math.pow(2, height);
   
10.         Integer[] array = new Integer[n];
    
11.         
    
12.         nodeQueue.offer(root);
    
13.         indexQueue.offer(1);
    
14.         
    
15.         while (!nodeQueue.isEmpty()) {
    
16.             TreeNode node = nodeQueue.poll();
    
17.             int index = indexQueue.poll();
    
18.             
    
19.             array[index] = node.val;
    
20.             
    
21.             if (node.left != null) {
    
22.                 nodeQueue.offer(node.left);
    
23.                 indexQueue.offer(2 * index);
    
24.             }
    
25.             
    
26.             if (node.right != null) {
    
27.                 nodeQueue.offer(node.right);
    
28.                 indexQueue.offer(2 * index + 1);
    
29.             }
    
30.         }
    
31.         
    
32.         return array;
    
33.     }
    
34.    
    
35.     private int getTreeHeight(TreeNode root) {
    
36.         if (root == null) {
    
37.             return 0;
    
38.         }
    
39.         
    
40.         int left = getTreeHeight(root.left);
    
41.         int right = getTreeHeight(root.right);
    
42.         
    
43.         return Math.max(left, right) + 1;
    
44.     }
    
45.    
    
46.     public static void main(String[] args) throws InterruptedException {
    
47.         Solution sol = new Solution();
    
48.         
    
49.         TreeNode root = new TreeNode(2);
    
50.         root.left = new TreeNode(4);
    
51.         root.right = new TreeNode(5);
    
52.         root.left.left = new TreeNode(6);
    
53.         root.right.left = new TreeNode(1);
    
54.         root.right.right = new TreeNode(7);
    
55.         root.left.left.left = new TreeNode(8);
    
56.         root.right.right.right = new TreeNode(9);
    
57.         
    
58.         Integer[] result = sol.compressTree(root);
    
59.         
    
60.         for (Integer e : result) {
    
61.             System.out.print(e + " ");
    
62.         }
    
63.         
    
64.         System.out.println("");
    
65.     }
    
66.    
    
67.    
    
68.     static class TreeNode {
    
69.         int val;
    
70.         TreeNode left, right;
    
71.         
    
72.         public TreeNode (int val) {
    
73.             this.val = val;
    
74.         }
    
75.     }
    
76. }

复制代码

lfzh123 发表于 2016-12-12 14:13
如果是比较稀疏的BT,可以存一下pre/post order+inorder.我觉得这样不错，因为只存了non-null的结点，size只 ...

用 preorder + inorder 存有一个很大的问题。 就是 duplicates不好处理。
请看 https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
重建binary tree的时候是assume no duplicates的。

我觉得如果是sparse BT, 直接serialize BT + "#" for null node 就完了。
或者两个arrays的办法也很好。

也可以用两个array，preorder存一个，inorder存一个， 回复起来也比较方便

格格笑 发表于 2016-11-18 10:29
heap  底层结构是数组  他在数组里的实现是左儿子 是2*i 右儿子是2*i + 1  希望你懂了~  如果不懂请看这 ...

但是这种解法要求这个二叉树是每一层都是满的而且最后一层元素都在最左侧。 实际Indeed问这个问题的时候， 他们的binary tree满足这个性质吗？

“Array 转化成 dense format，也就是说用两个array, 一个存值，一个存 值对应的index. ”

请问index是值在heap结构中的index吗？

请问  “用heap的方法”是什么意思？lz的code里并没有看到heap呀？

forestwn 发表于 2016-10-25 14:42
请问  “用heap的方法”是什么意思？lz的code里并没有看到heap呀？

heap  底层结构是数组  他在数组里的实现是左儿子 是2*i 右儿子是2*i + 1  希望你懂了~  如果不懂请看这个链接~
http://www.cse.hut.fi/en/researc ... ial/taulukkona.html

格格笑 发表于 2016-11-19 01:29
heap  底层结构是数组  他在数组里的实现是左儿子 是2*i 右儿子是2*i + 1  希望你懂了~  如果不懂请看这 ...

懂了 感谢！

如果是比较稀疏的BT,可以存一下pre/post order+inorder.我觉得这样不错，因为只存了non-null的结点，size只是所有non-null节点的两倍而已。