一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1400|回复: 6
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
butterwang 发表于 2016-2-16 04:16:44 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 博士 全职@Indeed - 网上海投 - Onsite |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
马上要去onsite了,看了一道Indeed 的高频面经:. 1point 3acres 璁哄潧
Store a binary tree to array, 怎么存节省空间?. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

我的理解是如果只寸binary tree的话,一个TreeNode 要存一个value, 已经两个pointer to left and right child, 大约占 12 byte。如果假设一个Pointer 也是4byte的话(32位系统)。. 1point 3acres 璁哄潧
我看网上大家的答案大部分都是用一个heap. 大体意思是如果这个tree 比较满的话,用一个array 来存就行, Node i 的 两个孩子的index 是 2*i, 2 * i + 1. 如果 i 从1开始的话。这样子一个node 只寸值,也就是只用了4 byte空间,原来的1/3.
但是如果这个tree比较稀疏的话,可以把这个稀疏Array 转化成 dense format,也就是说用两个array, 一个存值,一个存 值对应的index.
不知道还有没有其他更好的方法?
另外我把用 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<>();-google 1point3acres
  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();-google 1point3acres
  17.             int index = indexQueue.poll();
  18.             
  19.             array[index] = node.val;
  20.             . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  21.             if (node.left != null) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  22.                 nodeQueue.offer(node.left);
  23.                 indexQueue.offer(2 * index);
  24.             }. From 1point 3acres bbs
  25.             
  26.             if (node.right != null) {. 1point3acres.com/bbs
  27.                 nodeQueue.offer(node.right);
  28.                 indexQueue.offer(2 * index + 1);. 1point3acres.com/bbs
  29.             }
  30.         }
  31.         
  32.         return array;
  33.     }
  34.    
  35.     private int getTreeHeight(TreeNode root) {
  36.         if (root == null) {
  37.             return 0;. from: 1point3acres.com/bbs
  38.         }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  39.         
  40.         int left = getTreeHeight(root.left);
  41.         int right = getTreeHeight(root.right);
  42.         
  43.         return Math.max(left, right) + 1;. 1point3acres.com/bbs
  44.     }
  45.    
  46.     public static void main(String[] args) throws InterruptedException {. 鍥磋鎴戜滑@1point 3 acres
  47.         Solution sol = new Solution();. from: 1point3acres.com/bbs
  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);. from: 1point3acres.com/bbs
  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);. Waral 鍗氬鏈夋洿澶氭枃绔,
  57.         
  58.         Integer[] result = sol.compressTree(root);
  59.         
  60.         for (Integer e : result) {
  61.             System.out.print(e + " ");. From 1point 3acres bbs
  62.         }. Waral 鍗氬鏈夋洿澶氭枃绔,
  63.         
  64.         System.out.println("");
  65.     }
  66.    
  67.    
  68.     static class TreeNode {
  69.         int val;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  70.         TreeNode left, right;
    . more info on 1point3acres.com
  71.         
  72.         public TreeNode (int val) {
  73.             this.val = val;. Waral 鍗氬鏈夋洿澶氭枃绔,
  74.         }. 1point 3acres 璁哄潧
  75.     }
  76. }
复制代码
wlwhoami 发表于 2016-6-29 06:41:09 | 显示全部楼层
还请问楼主面的是哪个position?
回复 支持 反对

使用道具 举报

daniel123 发表于 2016-7-29 08:51:51 | 显示全部楼层
也可以用两个array,preorder存一个,inorder存一个, 回复起来也比较方便
回复 支持 反对

使用道具 举报

Zek_W 发表于 2016-9-9 12:22:26 | 显示全部楼层
“Array 转化成 dense format,也就是说用两个array, 一个存值,一个存 值对应的index. ”

请问index是值在heap结构中的index吗?
回复 支持 反对

使用道具 举报

forestwn 发表于 2016-10-25 14:42:48 | 显示全部楼层
请问  “用heap的方法”是什么意思?lz的code里并没有看到heap呀?
回复 支持 反对

使用道具 举报

格格笑 发表于 2016-11-19 01:29:19 | 显示全部楼层
forestwn 发表于 2016-10-25 14:42
请问  “用heap的方法”是什么意思?lz的code里并没有看到heap呀?

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

使用道具 举报

forestwn 发表于 2016-11-19 06:33:21 | 显示全部楼层
格格笑 发表于 2016-11-19 01:29
heap  底层结构是数组  他在数组里的实现是左儿子 是2*i 右儿子是2*i + 1  希望你懂了~  如果不懂请看这 ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
懂了 感谢!
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 06:48

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表