K*********n
发帖数: 2852 | 1 就是，不会考这种问题是吧。好久不复习数据结构，今天写一个非BST的二叉树，写着写
着就遇到这个问题了，手生，莫笑哈。 |
|
K*********n
发帖数: 2852 | 2 复杂度我觉得还好，这么写，如果是recursion的话。迭代的不好写。要是搞balance的
话，那就又复杂多了，再拓展到多叉树……哇哈哈 |
|
c********t
发帖数: 5706 | 3 响应号召，发中文题
二叉树求两结点间最大路径问题已经有很好解法。
现在有一个变体题，两点间最大路径必须要加上共同祖先到root这段。
比如：
3
/
4
/ \
1 2
结果为10
请问有什么好的解法？
我有一个笨解法，指数时间复杂度，为了不影响大家做题，会在跟帖贴出。 |
|
r*****e
发帖数: 146 | 4 二叉查找树中两个节点被错误的交换了，如何有效找出他们。有没有比较neat的解法？
谢谢 |
|
h****n
发帖数: 1093 | 5 inorder travese即可找第一个不对路和最后一个不对路的交换即可
二叉查找树中两个节点被错误的交换了，如何有效找出他们。有没有比较neat的解法？
谢谢
★ Sent from iPhone App: iReader Mitbbs Lite 7.56 |
|
|
g****y
发帖数: 240 | 7 是给一个值找一个节点，还是说随机返回二叉树中的一个节点？ |
|
r**h
发帖数: 1288 | 8 我猜lz想问的是二叉树使用stack/循环的pre-order traversal的实现？ |
|
x********9
发帖数: 7 | 9 要求要数组 实现二叉树 and implement following methods:
set(K, V)
get(K)
求教各位高手 |
|
|
|
|
p**t
发帖数: 157 | 13 不会用栈遍历二叉树的 你让他用栈做DFS不是更不会。。。 |
|
|
n****e
发帖数: 1677 | 15 看电影电视上做的弹弓好象都是用树叉做的，就是一根分成两根的那部分，不过我们都
用铁丝做，和和，大概以前没有铁丝所以用树叉，科学技术是第一生产力啊。我用八号
铁丝，就是最粗的那种，用钳子做成一个鼻子俩眼睛的样子(就象附图那样，现在的孩
子不要太幸福啊，连弹弓都可以买到了。不过铁丝没那么粗，也做的没那么标准)，然
后用硬的塑料丝把鼻子上面缠死，再找两根最粗的气门芯(大概有一厘米直径)穿过两个
眼睛再折回来，用硬的塑料丝绑紧，最后再用一跟硬毛皮，剪成大概两三厘米宽四五厘
米长，再在两头剪两个洞，把两根气门芯穿过小洞折回去，用硬塑料绑紧，弹弓就做成
了。弹子呢，可以用黄泥搓球，不过我喜欢捡小石头，到河边去捡小鹅卵石最好，黄泥
球走的比较直，小石头就会乱走，跟形状有关。我初中三年用自制弹弓杀生无数，大多
是小麻雀，那时候也不知道爱鸟，现在想起来很惭愧，所以自己后院挂喂鸟盒数个，希
望能弥补一下以前的罪过。阿弥陀佛。 |
|
j****z
发帖数: 1402 | 16 我家的邻居长了棵大树，侧枝都倒在了我们的车库上，我还得到他们同意后才请人的，
花了300刀雇人修了到我们这儿的叉叉而已，我们出的钱，没想过问他们要，他们也没
觉得要修。树太高所以雇人，看修的人爬得高高的，觉得花钱还是值得的。
没那么高的楼梯。
邻居还真要看人，不光是钱的问题，以后的关系也挺重要的。 |
|
C*********y
发帖数: 2738 | 17 那个树一般。不是什么时候都要看焦外，至少这个树叉叉看着很不幸。 |
|
d**********1
发帖数: 569 | 18 有，但是实现起来效率不高且麻烦。
C/C++的优点之一就是运行的速度和算法效率，所以有相当一部分人用C++就是为了算法
和速度，用算法的人多了，所以愿意讨论和实现的人就多了。
Basic PHP Python ...的和C++比起来，特点是入门容易，开发速度快，管理起来（相
对）简单。所以同时要用到这些语言和二叉树检索的机会太少了，用的少，基本也就没
人讨论了。
FORTRAN |
|
|
z*****a
发帖数: 9790 | 20 二叉树是一种数据结构，理论上任何编程语言都可以实现，只不过c/c++的指针实现起
来效率高
FORTRAN |
|
d******8
发帖数: 2191 | 21 好的数据结构基本都是在底层上实现，比如数据库搜索，页面搜索。MySQL的数据结构
是类似于二叉树的B-tree,B+tree，当然还有其他的结构像Hash。C++就是为了实现这些
底层的结构和算法的，所以C++很让人痛苦。网络编程就基本不用C++。
FORTRAN |
|
b**b
发帖数: 7 | 22 C++找到好的类库，也可以不用自己实现。
其他的语言也可以自己从头写一个二叉树。 |
|
|
x****o
发帖数: 21566 | 24 明明念C佳佳，Cxx里面的xx才是二叉树的意思。 |
|
d****o
发帖数: 32610 | 25 我以前搞C#的时候用的都是四叉树
FORTRAN |
|
x****o
发帖数: 21566 | 26 "你看，爸爸当时跟美国人结婚，一个美国人变成两个美国人。然后我们再分别结婚，
两个美国人变成四个美国人。然后我们再分别结婚，就有了8个美国人。这..."，老陈
顿了顿，指向白板，对着女儿说，“...就是一棵(满)二叉树”
“我可能要红了” -- 一包被拆开的卫生巾哆嗦着对其他卫生巾说
老师带学生过马路，小明突然捂住老师高耸的胸...老师：小明你干什么？ 小明：我扶
奶奶过马路！ 老师：滚！
当年高考第二门是数学，家长们都在嘱咐自家小孩认真审题好好检查，只有我妈说，“
能提前半小时交卷子吗？要不赶上晚高峰，太堵了”
今天我突然意识到超级马里奥很可能是个流浪汉。他每天醒来都穿同一身衣服，在下水
道里跑来跑去，揍别人抢他们的钱，然后你猜他拿钱干啥？买蘑菇
非主流强子惨遭女友抛弃，割腕自杀。妈妈抱着强子呜咽：老天爷啊你太不公平，我是
做了什么孽呀，你让我一个白发人送红、橙、黄、绿、蓝、靛、紫发人啊...
我有了一个惊人的发现刘备的两个儿子:刘封，刘禅连起来就是封禅，说明他有帝王之
心。孙坚的两个儿子:孙权，孙策连起来是权策，说明他善于权策。再来看看老曹家:曹
操，曹仁，曹真，曹爽曹家祖宗真是个... 阅读全帖 |
|
p*e
发帖数: 6785 | 27 上次google面试，一个大牛都不会reverse 二叉树
这海关居然问怎么balance bst
可能是一个马工专业去海关，被老黑老莫鄙视，身怀绝技怀才不遇，只好和书呆锁男得
瑟。 |
|
M********t
发帖数: 5032 | 28 人均2万元只吃汉堡 难怪
特朗普要打脸安倍(组图)
头条ABC
大实话
12小时32分钟前
近年日本的观光立国政策是搞得有声有色，优质的服务，实惠的价格，吸引了越来越多
的人来日本观光旅游，但大部分游客来日本就知道扎堆在电器店里买马桶盖，说起吃就
只能想到寿司或者拉面。
深度游的推广做得极其不到位，这可急坏了安倍。于是他一拍脑门，邀请一个流量
过亿的网红做个深度示范游吧，这个人就是川普。
于是就有了川普夫妇从11月5日到7日为期三天的正（shen）式（du）访（guan）问
（guang），名为加强日美同盟，实际上你懂的。
但安倍心有余而力不足，国库财政紧张，不能给川普最高礼遇——“国宾”，而是
作为“公式实务访问宾客”邀请来的。这其中有什么区别呢，请看下表。
另外，日本方会负担受邀方10人以内的出行费用，这一点不论是国宾还是访问宾客
都是一样的。这样看来其实两种都差不多呢，在日本，同一家餐厅午餐会比晚餐便宜，
想必皇宫内也是这样在算账的呢，真是勤俭持家。
当然这是开玩笑，真实理由大概是因为川普黑料太多了，日本国内很多人讨厌他。
在这几日的行程中就有不少民众反对游行，考虑到这一情况，安... 阅读全帖 |
|
m*******u
发帖数: 6052 | 29 反正也不能出门了，实况转播一下
这是我家后院的一棵三叉榆树，老虎第一次爬到一个树叉上，不算很高
今天爬得实在是太高了，在镜头外面
第一次，老虎在这个树叉上呆着，貌似心情不错，远眺呢
第二次，上了一个高高的小树枝，我只能仰拍了 |
|
S*******w
发帖数: 24236 | 30 赞。
集的一些常见二叉树面试问题（包括我亲身经历的）。多做多练习，相信你一定可以掌
握好。
left |
|
i***h
发帖数: 12655 | 31 这个是那本算法书二叉树一节后的题
网上查了下,除非节点带对父节点的指针才行,好象作弊了(这个额外的指针就是O(n)空
间了)
有答案么?
谢谢 |
|
c*********e
发帖数: 16335 | 32 按层遍历二叉树,无非就是把每个节点当作数组arr里的一個元素，一個index对应一個
节点。比如根节点index=０ (2的０次方 减 1）,第二层的最左边那个节点index=1 (2
的一次方 减 1）,第三层的最左边那个节点的index=3 (2的二次方 减 1 ）第四层的最
左边那个节点的index=7 (2的三次方 减 1）,etc.
所以，第一层就是arr[0]; (最左边节点index 0 为 2的０次方 减 1）
第二层就是arr[1]，arr[2]; (最左边节点index 1 为 2的1次方 减 1，最右边节点
index 2 为 下一层第一個节点的index（值为3） 减 1）
第三层就是arr[3]，arr[4],arr[5],arr[6]; (最左边节点index 3 为 2的2次方 减 1
，最右边节点index 6 为 下一层第一個节点的index（值为7） 减 1）
etc.
这样就可以按层遍历了。 |
|
m********t
发帖数: 13072 | 33 【 以下文字转载自 JobHunting 讨论区 】
发信人: moonlightt (月光妹妹), 信区: JobHunting
标 题: 二叉树
发信站: BBS 未名空间站 (Fri Oct 17 17:58:54 2014, 美东)
直到今年春季，我都不明白这词什么意思， 懒得理
某一天，无聊之际，查了一下对照英文，我考。。。 |
|
l****r
发帖数: 105 | 34 谢谢回复，不过我完全没看懂后半句
我的数组定义方式是
new int[] { 5, 4, 8, 11, -1, 13, 4, 7, 2, -1, -1, -1, -1, 5, 1 }
生成下面的二叉树
5
/
4 8
/ /
11 13 4
/ /
7 2 5 1 |
|
m******n
发帖数: 354 | 35 请问银行实际操作时有用binomial tree的吗，还是都用black-scholes公式啊？
如果有用二叉树的话， 是用JR的多还是用CRR的多呢？谢谢！ |
|
a*****s
发帖数: 6260 | 36 又仔细想了一下, 挖坑太累了! 假定是25个方的土. 一人一天一个方,
两个人得挖两周. 这还没算别的工作. 一个月下来能盖个大概就不错
了.
如果是完全在地上盖, 需要的只是树木而已. 我们有油锯, 选好了树
一通锯下去, 一天就能锯够树. 用一到两天把树干处理好, 或者可以跟
锯树同时进行. 我们有斧子和开山刀, 清理树叉够用了. 只需用油锯把
树裁成合适的长度, 然后挖出沟槽.
房子的修法可以参照这个地方:
http://architecture.about.com/od/periodsstyles/a/logcabins_2.htm
和这里:
http://outlands.tripod.com/farm/logcabin.htm
有油锯这些都能搞定啊. 油锯的排量不过几十CC, 一升油怎么也能用个
把小时. 我们带了5加仑油, 足够用了. |
|
f**********n
发帖数: 29853 | 37 很有可能。
另外就是树很牛叉，看看那些越野的视频，他们全靠树和绞盘。一根碗口粗的树就足够
支持一辆车的重量了。 |
|
i**********e
发帖数: 1145 | 38 更新，一道新面试题总结：
Largest BST in a Binary Tree
要求在树里找最大的 BST subtree。注意，这里指的是 subtree，如果不清楚定义，先
跟面试官确定一下。subtree 在维基百科的定义是指包括树节点和它所有的
descendents。做这题前必须知道怎么才能判断树是不是 BST。这题的巧妙之处在于利
用了 bottom-up 的 Depth-first 遍历来解决所有 top-down 遍历的难处。当然，如果
面试官要求的是 largest BST（不一定是 subtree），那就是另外一套思路了。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
o***e
发帖数: 28 | 39 树结构可以实现有序的元素访问 这一点hash不容易实现吧 : )
而且我觉得 树对数据结构和算法而言最大的贡献在于它优化后的高度总是 log(n) 从
而在很多 (用树来实现的) 有意思的算法里引入了对数复杂度的概念 比多项式复杂度
还是强很多 |
|
l*n
发帖数: 529 | 40 这里的二叉跟get/set一点关系都没有啊，后者根本就不是二叉的操作。 |
|
K*****k
发帖数: 430 | 41 空树的高度定义为0，单节点树的高度定义为1， 这里无须加2，画个图就知道了。 |
|
s******n
发帖数: 3946 | 42 应该充分利用排序的特性，假设第二颗树序列为n1,n2,n3....
n1插入第一颗树后，n2不用从顶端开始查，可以从n1插入位置开始向上搜索（前提是每
个node都有parent指针） |
|
p*****2
发帖数: 21240 | 43 post order, 最后一个值是root
从开始扫，比root小的是左树，后边的就是右树了，应该都比root的值大。
recursion就可以了吧？这是最straightforward的思路了。 |
|
k****r
发帖数: 807 | 44 厉害啊，
要是我在面试时遇到这个题，我就会
1,建立树，
2,in order读树，
3,判断是不是递增。
不会想到您这个方法。 |
|
y***n
发帖数: 1594 | 45 给一个二叉树,找到与给定节点距离为N的所有节点(没有parent link,有parent link),
两个节点间隔着几条边,就是距离为几。
如果一个树 （1 是root）
1
2 3
2 和3 的距离是不是2. |
|
h*******d
发帖数: 108 | 46 同问。
大概离墙根半米远的地方有棵桃树。树高两米左右，分了好几个叉。留着害怕对地基有
影响，砍了又觉得可惜。
一起请问这样的树会不会对房子的地基有影响呢? |
|
m***y
发帖数: 14763 | 47 死树用fork叉出来不费劲的。
老汉嚼的撸死没那么计较，你说什么都听你的。
但是死树总得扒出来啊，总得找地方扔啊，所以，不如就扔给撸死算了 ：） |
|
d*****d
发帖数: 10658 | 48 home insurance肯定管，打个电话就行了。找邻居砍树就难的多，我以前邻居大树倒了
把我家屋顶砸了个大窟窿，我让他砍，他就一直拖着，直到一年半后这树残存的另一截
把他自己的房顶砸了大窟窿他才立马全砍了个精光。 |
|
W*******s
发帖数: 18705 | 49 我朝Cover扔的，那里又是倒树又是石头，我损失了二个，一个是自己扔到高高的树叉
上去了，还穿过二颗树，没救了。还有一个挂掉了，如果用其它的东西估计损失还大。
基本上沉底之后，停一，二秒，往上下幅跳跃，停顿时间不长，有在跳跃之前咬的，有
在贴底慢游回来咬的。 |
|
g*********o
发帖数: 20357 | 50 那个mc可能是这个歌手的名字什么的
谁说青岛没有mc，我跟你说，有
别挖了别挖了别挖了，真惊了真惊了真惊了
青岛应该都认识我，因为我就是传说中的mc
我生在青岛，我长在青岛，我长大了要为青岛做点贡献
因为我现在是个mc，所以我得叨叨些个实质性的问题
青岛不是谁想挖就挖的，我看着那些街上的大洞我就来气
你说你要挖地老老实实挖你家去
你挖出个地动仪也没人管你
其实我一直觉得树它是个好东西
它可以净化空气挡风避雨
现在你要把树挖了去再种上去
原来世界园林都是这么来的
我们走向国际，我们牛不牛鼻
我们用40亿换个大森林
我们把草坪扒了去再种回去
我们把大桥地下都种上树林
想要看大海先爬个十来米
没事其实我们祖先都是树上的
俺们人行道现在是猴行道
你要在地上走头上就撞个包
以后学泰山，奥来奥来噢
欢迎来到森林青岛
我们的家，我们不喝啤酒我们不吃蛤蜊
我们以后全都在树上安家
俺们沙发是树叉，邻居是鸽子
要想吃饭我给你抓只蚂蚱
俺们没有很多钱，俺们没有很多地
俺们说什么话你都当放屁
俺们看好了哪一根就爬上去
反正现在房价那么贵俺也买不起
爱，就这么地
别挖了快别挖了，别挖了快别挖了
俺青岛那么美，别... 阅读全帖 |
|
