一亩三分地论坛

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

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

[算法题] 问一道google电面题

[复制链接] |试试Instant~ |关注本帖
又见紫风铃 发表于 2015-11-5 07:51:46 | 显示全部楼层 |阅读模式

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

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

x
求问下各位大神,怎么判断一个按照Preorder traversal serialized的binary tree的序列是否正确呢?不能deserialize成树比如
A) 9 3 4 # # 1 # # 2 # 6 # #是对的,因为表示
           9
         /   \
       3      2
      /  \      \
    4    1      6   
B ) 9 3 4 # # 1 # #就是错的,因为无法反构造回一棵树
robinyqiu 发表于 2015-11-7 14:46:48 | 显示全部楼层
我觉得可以在字符串里找"n##"这种结构(对应tree里两个children都是Null的叶节点),找到之后就把"n##"改写成"#",也就是把找到的那个末端的子树想想成null,最后字符串变成"#"的就是valid,否则就invalid
比如 A) 9 3 "4 # #" "1 # #" 2 # "6 # #" ---> 9 3 # # 2 # # ---> 9 "3 # #" "2 # #" ---> 9 # # ---> "9 # #" ---> "#"
       B) 9 3 "4 # #" "1 # #" ---> 9 3 # # ---> 9 "3 # #" ---> 9 # (没有"n##"结构了,return false)
不知道说清楚了没有

评分

2

查看全部评分

回复 支持 3 反对 0

使用道具 举报

dietpepsi 发表于 2016-1-16 11:04:30 | 显示全部楼层
本帖最后由 dietpepsi 于 2016-1-16 14:32 编辑

更好的做法是完全不用stack只需要一个计数,代表当前(总出度-总入度)的差值。
然后每一个node不论是不是null,都增加一个入度。区别在于如果不是null,则又需要两个子,即增加两个出度。
任何时刻这个计数不能小于0,否则return false; 并且最后此计数必须为0。
  1. public boolean isValidSerialization(String preorder) {
  2.     String[] nodes = preorder.split(",");
  3.     int diff = 1;
  4.     for (String node: nodes) {
  5.         if (--diff < 0) return false;
  6.         if (!node.equals("#")) diff += 2;
  7.     }
  8.     return diff == 0;
  9. }
复制代码

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

2006reload 发表于 2015-11-6 13:08:47 | 显示全部楼层
leetcode 255 verify-preorder-sequence-in-binary-search-tree/
回复 支持 反对

使用道具 举报

 楼主| 又见紫风铃 发表于 2015-11-7 06:06:06 | 显示全部楼层
2006reload 发表于 2015-11-6 13:08
leetcode 255 verify-preorder-sequence-in-binary-search-tree/

不太一样吧,不是BST而且是带mark的sequence,不知道思路会不会是类似的,表示木有想到
回复 支持 反对

使用道具 举报

2006reload 发表于 2015-11-13 14:51:49 | 显示全部楼层
嗯 我看错了
回复 支持 反对

使用道具 举报

programmingnerd 发表于 2016-1-5 14:22:41 | 显示全部楼层
try to reconstruct the tree from the preorder sequence, if cannot reconstruct a tree. then not correct. keep an counter (initial 0), if can correctly reconstruct, the final counter value will be the length of the original sequence. if counter is larger or smaller, the sequence is wrong.
回复 支持 反对

使用道具 举报

 楼主| 又见紫风铃 发表于 2016-1-5 21:28:47 | 显示全部楼层
programmingnerd 发表于 2016-1-5 14:22
try to reconstruct the tree from the preorder sequence, if cannot reconstruct a tree. then not corre ...

It is required not to try to reconstruct the tree
回复 支持 反对

使用道具 举报

dietpepsi 发表于 2016-1-16 04:47:34 | 显示全部楼层
本帖最后由 dietpepsi 于 2016-1-16 14:33 编辑

2 楼正解。
实现的话,可以用一个stack。贴一个我的实现。
这里假设字符串是逗号分隔,null一样是用'#'。
用了数组来模拟stack感觉好写一点儿,用Deque也是可以滴。复杂度是线性。
  1. public boolean isValidSerialization(String preorder) {
  2.         String[] values = preorder.split(",");
  3.         int n = values.length;
  4.         boolean[] isNull = new boolean[n]; // the stack
  5.         int end = 0; // end index
  6.         for (String value : values) {
  7.             if (end == 1 && isNull[0]) return false;
  8.             isNull[end++] = value.equals("#");
  9.             while (end >= 3 && !isNull[end - 3] && isNull[end - 2] && isNull[end - 1]) {
  10.                 isNull[end - 3] = true;
  11.                 end -= 2;
  12.             }
  13.         }
  14.         return end == 1 && isNull[0];
  15.     }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 02:44

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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