骨骼两轮店面

来发个面经 攒人品


第一轮国人姐姐 问的我lc307 解释了半天binary index tree 然后问Update sum的时间复杂度
我解释了半天我的树里结构是什么 估计姐姐对这个树也不是很熟
第二轮印度姐姐 问

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

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

:45):
我说反了 当时答得是preorder能reconstruct  inorder不能 不能的让举个反例就好了

coldsnow 发表于 2018-4-25 20:47
举个极端例子，bst中所有节点的元素全部相同，那如何复原？还是有前提，没有重复元素？

应该是没有重复元素的。 把preorder的结果一排序就是BST的inorder，然后就按常规做就行了

深海渔女 发表于 2018-4-26 20:41
bst定义上不可以有相同值的节点。我想你说的是不是binary tree？

我查了bst定义，并没有一个确定的答案，有的允许有重复，有的不允许。允许重复的有的左边<, 右边>=, 有的左边<=, 右边>=。 感觉如果考到了需要和面试官统一一下定义。

lz inorder traversal就是一个生序的数组，怎么能还原这个bst呢？感觉似乎是不能的

can you reconstruct a tree from in-order????? hmm

感觉只有给了preorder或者postorder才能还原bst啊

byrlhb 发表于 2018-4-24 08:39
lz inorder traversal就是一个生序的数组，怎么能还原这个bst呢？感觉似乎是不能的

我的想法和你一样，只给preorder，或者只给inorder都不能回复。可能考察的是lc药令吴

Yanainusa 发表于 2018-4-24 09:50
我的想法和你一样，只给preorder，或者只给inorder都不能回复。可能考察的是lc药令吴

我刚开始也以为是这个题 但是是binary search tree  不是binary tree

byrlhb 发表于 2018-4-24 08:39
lz inorder traversal就是一个生序的数组，怎么能还原这个bst呢？感觉似乎是不能的

umm 我好像说反了

dimi 发表于 2018-4-24 08:53
can you reconstruct a tree from in-order????? hmm

不好意思啊 说反了

楼主能讲下思路么？感觉就算是bst也没法还原啊

gqxcd 发表于 2018-4-24 21:43
我刚开始也以为是这个题 但是是binary search tree  不是binary tree

哦哦，不好意思，误解题意了。BST的话，楼主更改过的意思是，preorder可以，inorder不行，对吧。