10月28,K神开课讲数据科学,你来吗?


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 3782|回复: 15
收起左侧

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

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
马上要去onsite了,看了一道Indeed 的高频面经:. 鍥磋鎴戜滑@1point 3 acres
Store a binary tree to array, 怎么存节省空间?. from: 1point3acres.com/bbs

我的理解是如果只寸binary tree的话,一个TreeNode 要存一个value, 已经两个pointer to left and right child, 大约占 12 byte。如果假设一个Pointer 也是4byte的话(32位系统)。
我看网上大家的答案大部分都是用一个heap. 大体意思是如果这个tree 比较满的话,用一个array 来存就行, Node i 的 两个孩子的index 是 2*i, 2 * i + 1. 如果 i 从1开始的话。这样子一个node 只寸值,也就是只用了4 byte空间,原来的1/3.
但是如果这个tree比较稀疏的话,可以把这个稀疏Array 转化成 dense format,也就是说用两个array, 一个存值,一个存 值对应的index.
不知道还有没有其他更好的方法?. 1point 3acres 璁哄潧
另外我把用 heap 表示 binary tree的答案写出来。不知道对不对?
  1. import java.util.*;

  2. public class Solution {
  3.     private Queue<TreeNode> nodeQueue = new LinkedList<>();
  4.     private Queue<Integer> indexQueue = new LinkedList<>();
  5.     public Integer[] compressTree(TreeNode root) {
  6.         // step 1: get the height of the tree
  7.         int height = getTreeHeight(root);
  8.         int n = (int) Math.pow(2, height);
  9.         Integer[] array = new Integer[n];
  10.         
  11.         nodeQueue.offer(root);
  12.         indexQueue.offer(1);
  13.         
  14.         while (!nodeQueue.isEmpty()) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  15.             TreeNode node = nodeQueue.poll();
  16.             int index = indexQueue.poll();
  17.             
  18.             array[index] = node.val;
  19.             . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  20.             if (node.left != null) {
  21.                 nodeQueue.offer(node.left);
  22.                 indexQueue.offer(2 * index);
  23.             }
  24.             
  25.             if (node.right != null) {
  26.                 nodeQueue.offer(node.right);
  27.                 indexQueue.offer(2 * index + 1);
  28.             }
  29.         }
  30.         . visit 1point3acres.com for more.
  31.         return array;
  32.     }
  33.     . 鍥磋鎴戜滑@1point 3 acres
  34.     private int getTreeHeight(TreeNode root) {
  35.         if (root == null) {. From 1point 3acres bbs
  36.             return 0;
  37.         }
  38.         
  39.         int left = getTreeHeight(root.left);
  40.         int right = getTreeHeight(root.right);
  41.         
  42.         return Math.max(left, right) + 1;
  43.     }
  44.    
  45.     public static void main(String[] args) throws InterruptedException {
  46.         Solution sol = new Solution();
  47.         
  48.         TreeNode root = new TreeNode(2);
  49.         root.left = new TreeNode(4);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  50.         root.right = new TreeNode(5);
  51.         root.left.left = new TreeNode(6);
  52.         root.right.left = new TreeNode(1);
    . 1point3acres.com/bbs
  53.         root.right.right = new TreeNode(7);
  54.         root.left.left.left = new TreeNode(8);
  55.         root.right.right.right = new TreeNode(9);. Waral 鍗氬鏈夋洿澶氭枃绔,
  56.         
  57.         Integer[] result = sol.compressTree(root);
  58.         
  59.         for (Integer e : result) {
  60.             System.out.print(e + " ");
  61.         }
  62.         
  63.         System.out.println("");
  64.     }
  65.    
  66.    
  67.     static class TreeNode {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  68.         int val;
  69.         TreeNode left, right;
  70.         
  71.         public TreeNode (int val) {
  72.             this.val = val;
    . From 1point 3acres bbs
  73.         }
  74.     }
  75. }
复制代码

评分

2

查看全部评分

xiaofeng 发表于 2016-12-31 02:58:26 | 显示全部楼层
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 就完了。. 鍥磋鎴戜滑@1point 3 acres
或者两个arrays的办法也很好。
回复 支持 2 反对 0

使用道具 举报

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

使用道具 举报

格格笑 发表于 2016-11-19 01:29:19 | 显示全部楼层
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

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

头像被屏蔽
wlwhoami 发表于 2016-6-29 06:41:09 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

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呀?
回复 支持 反对

使用道具 举报

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

懂了 感谢!
回复 支持 反对

使用道具 举报

lfzh123 发表于 2016-12-12 14:13:06 | 显示全部楼层
如果是比较稀疏的BT,可以存一下pre/post order+inorder.我觉得这样不错,因为只存了non-null的结点,size只是所有non-null节点的两倍而已。
回复 支持 反对

使用道具 举报

AndrewFish 发表于 2016-12-19 09:05:26 | 显示全部楼层
格格笑 发表于 2016-11-18 10:29 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
heap  底层结构是数组  他在数组里的实现是左儿子 是2*i 右儿子是2*i + 1  希望你懂了~  如果不懂请看这 ...

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

使用道具 举报

lfzh123 发表于 2016-12-31 03:36:46 | 显示全部楼层
xiaofeng 发表于 2016-12-31 02:58
用 preorder + inorder 存有一个很大的问题。 就是 duplicates不好处理。
请看 https://leetcode.com/pr ...

是的,如果有duplicate的话,就不能用inorder+preorder了。
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-12-31 08:25:52 | 显示全部楼层
请问这个题和LC的serialize a binary tree有什么区别吗?
回复 支持 反对

使用道具 举报

忆梦前尘 发表于 2017-1-9 06:08:20 | 显示全部楼层
小A要当码农 发表于 2016-12-30 16:25
请问这个题和LC的serialize a binary tree有什么区别吗?

相比于LC 297,面试的时候这道题更在意于如何尽可能的压缩吧。。这样的话很多LC上面的用N来代替null node就很不好了。因为"N"是字符串,比int要占的多
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2017-1-9 06:16:06 | 显示全部楼层
忆梦前尘 发表于 2017-1-9 06:08
相比于LC 297,面试的时候这道题更在意于如何尽可能的压缩吧。。这样的话很多LC上面的用N来代替null node ...

那咋整啊? 有啥好的idea么? 用int比较难吧?
回复 支持 反对

使用道具 举报

忆梦前尘 发表于 2017-1-9 06:54:39 | 显示全部楼层
小A要当码农 发表于 2017-1-8 14:16
那咋整啊? 有啥好的idea么? 用int比较难吧?

用int[] 比较好,因为每个node从12byte降到了4个byte,相对位置用index就可以表示。目前来看,上面的heap方法是最佳办法,就是用int数组来实现,左右孩子就是2i,2i+1。
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2017-1-9 11:18:00 | 显示全部楼层
忆梦前尘 发表于 2017-1-9 06:54. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
用int[] 比较好,因为每个node从12byte降到了4个byte,相对位置用index就可以表示。目前来看,上面的heap ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
多谢 我研究一下哈
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-9-20 03:17

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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