j****c 发帖数: 19908 | 1 先是前段时间跑步把脚趾甲戳到肉里了,现在天天只能穿凉鞋一瘸一拐的;前天开始长
智齿,疼死我了,晚上睡觉都会被疼醒。今早快天亮的时候疼醒起来吃了个止疼药继续
睡,一会儿有人来敲门,我还以为是从王神医那里买的CF卡送到了呢,原来是
apartment管理员,说昨晚风雨大作,一个大树叉被劈了,问我那辆黑色的大众是不是
你家的。
靠,可不是吗?新买的VW Tiguan阿,赶紧拿着相机下楼去看看。不过还好,旁边那辆
full size的美国车承担了绝大部分树叉的重量,我的车现在大略看了下没啥damage。
刚打了电话给保险公司,现在在等apartment叫人来把树叉移走再仔细检查下。
顺便问下万佛,这种被树砸了,但表面没什么damage的,会不会内部有什么损坏阿?需
要怎么检查?保险公司后天会联系我询问一些车况 |
|
G***n 发帖数: 877 | 2 二叉树是数据结构,很多语言library的container很多都是二叉树的结构,比如c++里
STL的Map,所以你要知道这个。
FORTRAN |
|
M*P 发帖数: 6456 | 3 二叉树显然是C++的核心
C++里面的++就是二叉树的意思。
★ 发自iPhone App: ChineseWeb 7.8 |
|
b***u 发帖数: 12010 | 4 原楼主其实是牛人. c++ stl的map是2叉树写的,其他的java用的hash table,其他不
清楚,可能也不是2叉树。
FORTRAN |
|
c*********e 发帖数: 16335 | 5 如果table的每行数据是以二叉树结构存在硬盘里,那么我删去一行数据之后,这行的
primary key对应的数据是空的。比如现在有100行数据在一个表里,我删去了
primary key是keyid=5的那一行数据,那么我再加新的一行数据进这个表,新的数据的
keyid应该是5,而不是101,对不对?
但是,在使用mysql之类数据库的时候,现在有100行数据在一个表里,我删去了
primary key是keyid=5的那一行数据,那么我再加新的一行数据进这个表,新的数据的
keyid是101。 这说明数据不是按照二叉树存储在硬盘里的。
到底怎么回事呢?mysql, oracle,sql server,每个数据库软件不一样? |
|
S***w 发帖数: 1014 | 6 非常好的计算机算法内容博客,
多谢分享
集的一些常见二叉树面试问题(包括我亲身经历的)。多做多练习,相信你一定可以掌
握好。我会在这里更新和添加常见到的二叉树问题。
left |
|
K*****k 发帖数: 430 | 7 定义直径为连通两节点最多的边数
空树和单节点树的直径都是0
直径有可能通过根节点,也可能通过某棵子树的根节点但不通过根节点。
利用经典的求二叉树高度的递归函数,同时保持直径的最大值,就可以了么?
// The initial value of diameter is set to 0
int Depth(Node* root, int& diameter)
{
if (root == NULL)
return 0;
int LDepth = Depth(root->left, diameter);
int RDepth = Depth(root->right, diameter);
if (LDepth + RDepth > diameter)
diameter = LDepth + RDepth;
return max(LDepth + 1, RDepth + 1);
} |
|
c*****e 发帖数: 3226 | 8 把这个题的答案帖一下吧。
句话说,二叉树最高深度和最低深度的值相差不超过1 是 二叉平衡树 的 充分 而非
必要 条件
的一个真子集。
树概念的理解。 |
|
c***g 发帖数: 472 | 9 给定一个inorder和preorder构建一颗二叉树
如果,这里面有duplicated的元素,请问如何做?还是根本做不了? 因为你无法在
inorder里面判断哪个是左树还是右树啊 |
|
c***g 发帖数: 472 | 10 给定一个inorder和preorder构建一颗二叉树
如果,这里面有duplicated的元素,请问如何做?还是根本做不了? 因为你无法在
inorder里面判断哪个是左树还是右树啊 |
|
O******i 发帖数: 269 | 11 你那个是Crackcode第四版或者更早版本中的定义,是错的,是充分而非必要条件。按
照那样太过于严格的定义,会把一些是平衡树的也判定为不是平衡树,造成false
negative。
在第五版中改正过来了。 |
|
z****e 发帖数: 54598 | 12 r是高阶语言,哪里用来算什么大数据
用来表达一些idea还差不多
真正计算都是压给那些pkg,比如scipy或者hadoop这些
r全部load数据到内存,根本算不出来
mysql底层实现就用了b-tree
c主要用来写一些底层的软件,os, db还有jvm, r这些
其它语言相对c是一种高阶的存在
最后一句是对的
其它语言甚至都不是二叉树是语言的一部分
而是hashtable这种结构是语言的一部分了
全部都是key-value pair,所有语言,到底层都是c
只有一些相对类库比较全的语言,你才能容易找到树结构
比如java里面就有treemap,但是treemap使用次数比起hashmap来说
那不知道是要小多少倍,人类发展这么多年,树有些old了
前面有人说set,set也可以多种实现,treeset比起hashset来说
我估计很多人甚至都不知道有treeset这个类
类似的还有list,arraylist比起linkedlist来说,要常用太多 |
|
w********2 发帖数: 632 | 13 我和我爹基因树叉的距离当然是我爹的遗传影响,因为有父子关系另一种数据证明。但
我和猴子的基因树叉的距离就是种间差距了,硬套上进化,没有理由啊。起码从基因树
上看不出因果关系来。 |
|
h*****g 发帖数: 312 | 14 7
/ \
8 9
\ / \
5 4 6
inorder: 857496
BFS: 789645
如何 重构这个二叉树,然后求树的宽度(哪一层node最多?) |
|
g****u 发帖数: 252 | 15 我觉得你的算法是对的. 一个小优化是找两个subarray的分界点可以用二分查找. 但是
在递归过程中必须维护当前子树的值的上下界,一旦越界就报错. 我觉得不值得这么折
腾.
还有一个办法就是反向读数组, 然后重建BST. 每读一个数都应该可以找到二叉树中唯
一插入的位置, 如果找不到的话就报错. 但是找插入位置的过程的复杂度至少是树的高
度,也就是O(log N), 所以总体还是O(N logN), 实现的复杂度就差多了. |
|
j***a 发帖数: 1100 | 16 平衡二叉树有很多种方法吧。
最简单的应该是avl 树。 |
|
c****p 发帖数: 6474 | 17 你说的应该是二叉搜索树BST。
有些数据结构的底层实现实际上是用BST及其变种实现的,你没有直观地看到BST而已。
就我所知,C++里面的set是用红黑树(平衡BST)实现的。
FORTRAN |
|
y***d 发帖数: 126 | 18 房前房后各有一颗树要看。两颗树都有倒下的空间。先说前院的。树高大约20尺。分了
三个小叉,等于是三棵树。最粗的地方直径大约7寸的样子。如果让树直接倒下来是落
在driveway上,不知道会不会对driveway有损伤?我在落点堆一些纸箱子会不会有帮助?
后院的树难度大一些,树高大约30-35尺高,也是分了三叉,等于是三颗树,底部最粗
的地方10寸。这个要拉绳子来控制落下来的位置。落点是草坪,会破坏草坪吗?我本来
想站在屋顶用pole saw争取先把顶端细的那一部分据下来,这样就可以从上往下一节一
节的锯,但是一是pole saw可能够不到,二是站在屋顶斜坡上还是挺吓人的。可能还是
cut and fall最靠谱。
这活我要是找专业砍树的他们会用什么方法?多少钱算是合理? |
|
|
d********w 发帖数: 363 | 20 bool isSubTree(Tree* large, Tree * small);
假设就是二叉树吧,想到一个思路,把两个树按先序和中序打印出来,然后查看是否是
substr,能证明这样是对么?或者还有什么其他思路?感觉树的查找是个挺难的问题,
之前我在工作中就遇到过在一个domtree中,如何比较树的相似度,
就是比如把网页按dom解析,形成一个树,判断两个网页的duplicate,可以转化成求这
两个树的相似度,这又有2个问题,如何做树的查找,如何计算相似。不知大家有没有
做过这方面研究的
它的一个简化版本就是这题 |
|
|
i**********e 发帖数: 1145 | 22 Print Edge Nodes (Boundary) of a Binary Tree
问题是要把树的周围counter-clockwise打印出来。先打印root,然后从上到下打印最
左边的节点,然后从左到右的顺序打印叶子节点,然后从下到上打印最右边的节点。这
题的精粹就在于使用depth-first traversal,一个递归就能搞定。先把树分为两个树
(root的左孩子和右孩子)处理。先处理左树,再处理右树。如果卡在怎么从下到上打
印最右边节点,可以想想post-order traversal。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
r******l 发帖数: 10760 | 23 我是CS科班出身的,但是以前从来没听说过红黑树,看到大家经常提到,才去大概看了
看。虽然没弄很清楚,但是感觉并不是很好啊。不知道为什么clrs这么经典的教材,平
衡二叉树的唯一的例子选了红黑树呢?国内的课本应该都是讲AVL树吧?
这个红黑树很常用么?面试常碰到么? |
|
a*****s 发帖数: 6260 | 24 “同志们,照这么下去,我们很快就得肥的拖瘦,瘦的拖死,然后一起呜
呼哀哉了。”我平视前方,二目无神地说道。现在的时间是D+5日的早上。虽
然睡了一觉,但还是觉得浑身酸痛,恨不能再大睡个三天四夜什么的。大家都
起来了。身边不远AUV在用清水漱口,StupidMIT在拨弄火堆。剩下的人散落
各处在忙着,没人理我的喳。
“我们得改进措施。”我最后总结发言道。
所谓改进,就是不再抬树,改为拉树。先在树干下垫上一些比较圆的木棍,
然后树叉也留两根下来用来拉。由六个人抬改为两个人拉,两个人垫木棍,
剩下两个人看着——不全是看着,还要拿枪警戒,还要看下山的道,隔一段还
要换人。克服这个滚动摩擦费的力果然比克服地球引力做功要简单,一上午
大家伙弄下来八、九棵树。中午吃饭休息的时候,大家很乐观地估计,只需要
八、九天就能把树全部弄下来了。然后再用个十几天把房子盖起来,估计也
就差不多了。
下午吃了饭继续干。我看着满山倒伏的树木就开始运气。这么多树,得拉到
什么时候。忽然间我想起一个笑话:拉不动就滚吧!我目视了一下,决定先把
近没有阻挡的这些树全都给横着滚下去,怎么着也有好几十棵了。 |
|
d******a 发帖数: 32122 | 25 那还是上个世纪九十年代初的事,在那个年代,路用通勤车还都在开行,对于我这
样一个火车迷来说是件非常好的事情。因为在那时,电脑、网络、数码相机是些很遥远
的东西,时常出来坐坐通勤车,对我来说就已经很幸福了。虽然能见到的只有当时路上
运行的机车、车辆,但那强大的诱惑使我每次登上通勤车时都从不感到枯燥,总有新鲜
的感觉。在那个年轻而极富感情色彩的年龄段里给我留下了不可磨灭的回忆。
其中与我最亲密的,留下最深印象的便是每晚7:23从老京包线沙河站发车经西北环
至丰沙线三家店站的路用通勤车。多少年了,虽然当年的车次早已忘记,但这趟车每每
出现在我回忆中时,那段美好的时光便完美再现于梦境般的回忆中。
那时的我在北京动物园就职,专职负责照顾国宝大熊猫的幼仔,工作谈不上多辛苦
,但责任和细心是不可缺少的,同时也为这份工作感到自豪。白天与可爱的熊猫宝宝思
守,虽然晚上有时也要值夜班。但还是有很多闲暇的时间的,当时不与父母同住,又没
有女朋友,一个人自在快乐,无忧无虑,精力充沛得无处发泄时,下了班就想出去坐火
车散心。动物园离北站很近,北站的通勤车无疑成了我坐车的首选。
那时北站北... 阅读全帖 |
|
d******a 发帖数: 32122 | 26 那还是上个世纪九十年代初的事,在那个年代,路用通勤车还都在开行,对于我这
样一个火车迷来说是件非常好的事情。因为在那时,电脑、网络、数码相机是些很遥远
的东西,时常出来坐坐通勤车,对我来说就已经很幸福了。虽然能见到的只有当时路上
运行的机车、车辆,但那强大的诱惑使我每次登上通勤车时都从不感到枯燥,总有新鲜
的感觉。在那个年轻而极富感情色彩的年龄段里给我留下了不可磨灭的回忆。
其中与我最亲密的,留下最深印象的便是每晚7:23从老京包线沙河站发车经西北环
至丰沙线三家店站的路用通勤车。多少年了,虽然当年的车次早已忘记,但这趟车每每
出现在我回忆中时,那段美好的时光便完美再现于梦境般的回忆中。
那时的我在北京动物园就职,专职负责照顾国宝大熊猫的幼仔,工作谈不上多辛苦
,但责任和细心是不可缺少的,同时也为这份工作感到自豪。白天与可爱的熊猫宝宝思
守,虽然晚上有时也要值夜班。但还是有很多闲暇的时间的,当时不与父母同住,又没
有女朋友,一个人自在快乐,无忧无虑,精力充沛得无处发泄时,下了班就想出去坐火
车散心。动物园离北站很近,北站的通勤车无疑成了我坐车的首选。
那时北站北... 阅读全帖 |
|
m**********e 发帖数: 12525 | 27 你这思想方式,永远成不了科学家啊
观测恒星和太阳升起时间的变化,比如,恒星升起的时后太阳与远方树叉同高,这样树
叉能多少等分天穹,就能不借助时钟完成测量
? |
|
q*******n 发帖数: 20306 | 28 在北美混的滋润的傻叉们不知道,中国的人都是自己砍树,没有雇树木公司来砍树的说
法。
中国农村经常在小孩出生时种树,等到小孩长大结婚时,树也长大了,正好砍了造新房
,造房砍树都是村民自己动手,当然亲戚也会来帮忙。 |
|
|
g*******y 发帖数: 1930 | 30 对的。
这个方法是我以前做一道完全二叉树/DFS的时候的方法,昨天面挂了过度沮丧,今天就头晕了随口说了。。。 |
|
r****o 发帖数: 1950 | 31 用书上通用的用queue的方法实现二叉树按层次打印,结果全打印到一行了。
不知道有没有什么好办法可以插入换行符,让每层数据在不同的行显示? |
|
c******f 发帖数: 2144 | 32 这个应该等价二叉树的遍历
那么T(n)=2T(n/2)+O(1)
适用master theory的其中一种情况
当有ε > 0, 使得f(n)=O(n^(logb(a)-ε))则T(n)=Theta(n^logb(a))
这里a=2,b=2,logb(a)=1, f(n)=O(1), 所以存在epsilon=1
那么 T(n)=Theta(n) |
|
A*********r 发帖数: 564 | 33 不错,正在复习这一块。。
谢谢分享和总结。。
集的一些常见二叉树面试问题(包括我亲身经历的)。多做多练习,相信你一定可以掌
握好。
left |
|
s*******t 发帖数: 248 | 34 常看楼主博客,收获很大,谢谢!
集的一些常见二叉树面试问题(包括我亲身经历的)。多做多练习,相信你一定可以掌
握好。
left |
|
h******3 发帖数: 351 | 35 请问能否share
Binary Search Tree In Order Iterative Traversal without using a visited flag
的方法?
集的一些常见二叉树面试问题(包括我亲身经历的)。多做多练习,相信你一定可以掌
握好。
left |
|
s**a 发帖数: 131 | 36 Thanks.
集的一些常见二叉树面试问题(包括我亲身经历的)。多做多练习,相信你一定可以掌
握好。
left |
|
i**********e 发帖数: 1145 | 37 更新:
Finding the Maximum Height of a Binary Tree
这题就是寻找二叉树的最深度,利用DFS可以轻松解决。挑战的是:如何写非递归的版
本。有两种解法,一是用BFS,解法比较直接。另一种解法是转换成非递归BFS,方法请
参考In-Order Traversal Iterative Solution.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
t*****j 发帖数: 1105 | 38 对于遍历二叉树的复杂度,一直有疑问。
先根遍历应该是O(n)吧,中根和后根呢? |
|
b*******8 发帖数: 37364 | 39 In Order(先左再右边)遍历,访问左孩子则记录1,访问右孩子记录2,返回父节点记
录为0,得到一个记录串。
再来一次镜像操作:
In Order(先右边左边)遍历,访问右孩子则记录1,访问左孩子记录2,返回父节点记
录为0。
两次操作得到的记录一样,则对称。事实上,做第二次遍历时,只要时时跟第一的结果
比较,一旦发现不同马上就知道不对称,退出。此方法可简单扩展到N叉树。 |
|
i******t 发帖数: 158 | 40 还是按楼主的方法,加上dummy node, 变成完全二叉树, 就可以了 |
|
a********m 发帖数: 15480 | 41 binary tree用递归应该可以吧。每个节点相等,左子树和右子树交叉相等就可以了。
bool mirrow(node* p1, node* p2)
{
if(!p1 && !p2) return true;
if(!p1 || !p2 )return false;
return p1->data == p2->data && mirrow(p1->left, p2->right) && mirrow(p1->
right, p2->left);
}
调用!root || mirrow(root->left,root->right);就可以了。
n叉树应该类似。 |
|
|
L***Q 发帖数: 508 | 43 如果有duplicate,应该是无法唯一确定。一个三个node的例子:3 3 3.前序中序都这
结果,可以有好几种二叉树。 |
|
L***Q 发帖数: 508 | 44 如果有duplicate,应该是无法唯一确定。一个三个node的例子:3 3 3.前序中序都这
结果,可以有好几种二叉树。 |
|
p*****2 发帖数: 21240 | 45 看了看,感觉应该可以分两段。
BFS 可以看出7是root
indorder可以看出85是左树,496是右树
BFS又可以看出,8是左树的根,9是右树的根
7
/ \
8 9
\ / \
5 4 6
inorder: 857496
BFS: 789546 |
|
|
|
p********n 发帖数: 20 | 48 首先遍历一下求出两棵树的欧拉序列;问题转化求两个序列的最长*连续*公共子串。
但是由于两棵树是独立编号的,这导致两棵树中structure相同的子树在各自的欧拉序
列中可能相差一个常数;所以需要处理一下欧拉序列,可以这样变换:(A[0],...,A[n-
1])-->(A[1]-A[0],...,A[n-1]-A[n-2])。
剩下的就是求最长连续公共子串,可以后缀数组搞定。
整个过程中,遍历O(n+m),求最长连续公共子串O(n+m),所以总复杂度也是O(n+m)。n,
m是两棵树的节点数。 |
|
p********n 发帖数: 20 | 49 对二叉树进行DFS,将遍历过程中遇到的节点按顺序记下,得到一个长度为2N-1的节点
序列,就是欧拉序列。 |
|