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对应的数据是空的。比如现在有1００行数据在一个表里，我删去了
primary key是keyid=5的那一行数据，那么我再加新的一行数据进这个表，新的数据的
keyid应该是5，而不是101,对不对？
但是，在使用mysql之类数据库的时候，现在有1００行数据在一个表里，我删去了
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的节点
序列，就是欧拉序列。 |
|
