i******t
发帖数: 158 | 1 还是按楼主的方法,加上dummy node, 变成完全二叉树, 就可以了 |
|
L***Q
发帖数: 508 | 2 如果有duplicate，应该是无法唯一确定。一个三个node的例子：3 3 3.前序中序都这
结果，可以有好几种二叉树。 |
|
L***Q
发帖数: 508 | 3 如果有duplicate，应该是无法唯一确定。一个三个node的例子：3 3 3.前序中序都这
结果，可以有好几种二叉树。 |
|
|
|
p********n
发帖数: 20 | 6 对二叉树进行DFS，将遍历过程中遇到的节点按顺序记下，得到一个长度为2N-1的节点
序列，就是欧拉序列。 |
|
K*********n
发帖数: 2852 | 7 就是，不会考这种问题是吧。好久不复习数据结构，今天写一个非BST的二叉树，写着写
着就遇到这个问题了，手生，莫笑哈。 |
|
c********t
发帖数: 5706 | 8 响应号召，发中文题
二叉树求两结点间最大路径问题已经有很好解法。
现在有一个变体题，两点间最大路径必须要加上共同祖先到root这段。
比如：
3
/
4
/ \
1 2
结果为10
请问有什么好的解法？
我有一个笨解法，指数时间复杂度，为了不影响大家做题，会在跟帖贴出。 |
|
|
g****y
发帖数: 240 | 10 是给一个值找一个节点，还是说随机返回二叉树中的一个节点？ |
|
r**h
发帖数: 1288 | 11 我猜lz想问的是二叉树使用stack/循环的pre-order traversal的实现？ |
|
x********9
发帖数: 7 | 12 要求要数组 实现二叉树 and implement following methods:
set(K, V)
get(K)
求教各位高手 |
|
|
|
|
p**t
发帖数: 157 | 16 不会用栈遍历二叉树的 你让他用栈做DFS不是更不会。。。 |
|
|
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才是二叉树的意思。 |
|
x****o
发帖数: 21566 | 25 "你看，爸爸当时跟美国人结婚，一个美国人变成两个美国人。然后我们再分别结婚，
两个美国人变成四个美国人。然后我们再分别结婚，就有了8个美国人。这..."，老陈
顿了顿，指向白板，对着女儿说，“...就是一棵(满)二叉树”
“我可能要红了” -- 一包被拆开的卫生巾哆嗦着对其他卫生巾说
老师带学生过马路，小明突然捂住老师高耸的胸...老师：小明你干什么？ 小明：我扶
奶奶过马路！ 老师：滚！
当年高考第二门是数学，家长们都在嘱咐自家小孩认真审题好好检查，只有我妈说，“
能提前半小时交卷子吗？要不赶上晚高峰，太堵了”
今天我突然意识到超级马里奥很可能是个流浪汉。他每天醒来都穿同一身衣服，在下水
道里跑来跑去，揍别人抢他们的钱，然后你猜他拿钱干啥？买蘑菇
非主流强子惨遭女友抛弃，割腕自杀。妈妈抱着强子呜咽：老天爷啊你太不公平，我是
做了什么孽呀，你让我一个白发人送红、橙、黄、绿、蓝、靛、紫发人啊...
我有了一个惊人的发现刘备的两个儿子:刘封，刘禅连起来就是封禅，说明他有帝王之
心。孙坚的两个儿子:孙权，孙策连起来是权策，说明他善于权策。再来看看老曹家:曹
操，曹仁，曹真，曹爽曹家祖宗真是个... 阅读全帖 |
|
p*e
发帖数: 6785 | 26 上次google面试，一个大牛都不会reverse 二叉树
这海关居然问怎么balance bst
可能是一个马工专业去海关，被老黑老莫鄙视，身怀绝技怀才不遇，只好和书呆锁男得
瑟。 |
|
S*******w
发帖数: 24236 | 27 赞。
集的一些常见二叉树面试问题（包括我亲身经历的）。多做多练习，相信你一定可以掌
握好。
left |
|
i***h
发帖数: 12655 | 28 这个是那本算法书二叉树一节后的题
网上查了下,除非节点带对父节点的指针才行,好象作弊了(这个额外的指针就是O(n)空
间了)
有答案么?
谢谢 |
|
c*********e
发帖数: 16335 | 29 按层遍历二叉树,无非就是把每个节点当作数组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 | 30 【 以下文字转载自 JobHunting 讨论区 】
发信人: moonlightt (月光妹妹), 信区: JobHunting
标 题: 二叉树
发信站: BBS 未名空间站 (Fri Oct 17 17:58:54 2014, 美东)
直到今年春季，我都不明白这词什么意思， 懒得理
某一天，无聊之际，查了一下对照英文，我考。。。 |
|
l****r
发帖数: 105 | 31 谢谢回复，不过我完全没看懂后半句
我的数组定义方式是
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 | 32 请问银行实际操作时有用binomial tree的吗，还是都用black-scholes公式啊？
如果有用二叉树的话， 是用JR的多还是用CRR的多呢？谢谢！ |
|
c****p
发帖数: 6474 | 33 你说的应该是二叉搜索树BST。
有些数据结构的底层实现实际上是用BST及其变种实现的，你没有直观地看到BST而已。
就我所知，C++里面的set是用红黑树（平衡BST）实现的。
FORTRAN |
|
b***u
发帖数: 12010 | 34 原楼主其实是牛人. c++ stl的map是2叉树写的，其他的java用的hash table，其他不
清楚，可能也不是2叉树。
FORTRAN |
|
b*******8
发帖数: 37364 | 35 In Order(先左再右边）遍历，访问左孩子则记录1，访问右孩子记录2，返回父节点记
录为0，得到一个记录串。
再来一次镜像操作：
In Order(先右边左边）遍历，访问右孩子则记录1，访问左孩子记录2，返回父节点记
录为0。
两次操作得到的记录一样，则对称。事实上，做第二次遍历时，只要时时跟第一的结果
比较，一旦发现不同马上就知道不对称，退出。此方法可简单扩展到N叉树。 |
|
|
l*n
发帖数: 529 | 37 这里的二叉跟get/set一点关系都没有啊，后者根本就不是二叉的操作。 |
|
a********m
发帖数: 15480 | 38 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叉树应该类似。 |
|
s******n
发帖数: 3946 | 39 应该充分利用排序的特性，假设第二颗树序列为n1,n2,n3....
n1插入第一颗树后，n2不用从顶端开始查，可以从n1插入位置开始向上搜索（前提是每
个node都有parent指针） |
|
K*********n
发帖数: 2852 | 40 复杂度我觉得还好，这么写，如果是recursion的话。迭代的不好写。要是搞balance的
话，那就又复杂多了，再拓展到多叉树……哇哈哈 |
|
d****o
发帖数: 32610 | 41 我以前搞C#的时候用的都是四叉树
FORTRAN |
|
r*****8
发帖数: 2560 | 42 “最后，希望你能继续努力学习C++。语言学习不在数量，在于质量。能够精通一门比
泛泛学习多门语言更有意义，也更见功力。”
谢谢指点！
“语言学习不在数量，在于质量。”
这些语言都是被逼无奈才学的，工作需要，不同平台，不同环境，只好继续学。数据处
理完了，或者是达到目的了，就不用了。
“你所说的其他语言没有用，可能性有两个：第一，你没有用；第二，你没有显示的用
，但是事实上你所用的函数已经帮你完成了这些工作。”
我很同意，Python、R里面建立多维矩阵，数据量也很大，只是一个命令，没说怎么建
的。搜索多维矩阵，也只是一个函数，没显示怎么搜索。估计里面用到了二叉结构。
： 最后，希望你能继续努力学习C++。语言学习不在数量，在于质量。能够精通一门比泛
： 泛学习多门语言更有意义，也更见功力。 |
|
K*****u
发帖数: 241 | 43 判断一棵二叉树是否平衡
在第五版前Gayle认为只需要判断最高深度和最低深度的值是否相差不超过1就可以。
解法虽然简单，但偷换了概念，是错误的
虽然最高深度和最低深度的值相差不超过1的树一定是平衡的，但反过来却不对。换句话说，二叉树最高深度和最低深度的值相差不超过1 是 二叉平衡树 的 充分 而非 必要 条件
也就是说那个解法偷换成了更强的要求（虽然解法更简单)，但这样的树只是平衡树的一个真子集。
请大家自行构造一棵最大深度和最小深度的值超过1的二叉平衡树，加深对二叉平衡树概念的理解。 |
|
l*********8
发帖数: 4642 | 44 逐个扫描数组元素，依次插入下面这样的二叉树
struct BinaryTreeNode {
int subNodeCount;
int val;
BinaryTreeNode * left;
BinaryTreeNode * right;
};
在插入元素x[i]的同时，也容易求得二叉树中比x[i]小的元素的数目k[i], 也就是比x[
i]小，并且位于x[i]之前的元素个数.
swap总数就是： sum(x[i] - k[i]), i from 0 to n-1
每次插入二叉树， O(logn)
n个元素， 总共 O(n*logn) |
|
c*****e
发帖数: 3226 | 45 把这个题的答案帖一下吧。
句话说，二叉树最高深度和最低深度的值相差不超过1 是 二叉平衡树 的 充分 而非
必要 条件
的一个真子集。
树概念的理解。 |
|
O******i
发帖数: 269 | 46 你那个是Crackcode第四版或者更早版本中的定义，是错的，是充分而非必要条件。按
照那样太过于严格的定义，会把一些是平衡树的也判定为不是平衡树，造成false
negative。
在第五版中改正过来了。 |
|
r*****e
发帖数: 146 | 47 二叉查找树中两个节点被错误的交换了，如何有效找出他们。有没有比较neat的解法？
谢谢 |
|
h****n
发帖数: 1093 | 48 inorder travese即可找第一个不对路和最后一个不对路的交换即可
二叉查找树中两个节点被错误的交换了，如何有效找出他们。有没有比较neat的解法？
谢谢
★ Sent from iPhone App: iReader Mitbbs Lite 7.56 |
|
d********w
发帖数: 363 | 49 bool isSubTree(Tree* large, Tree * small);
假设就是二叉树吧，想到一个思路，把两个树按先序和中序打印出来，然后查看是否是
substr，能证明这样是对么？或者还有什么其他思路？感觉树的查找是个挺难的问题，
之前我在工作中就遇到过在一个domtree中，如何比较树的相似度，
就是比如把网页按dom解析，形成一个树，判断两个网页的duplicate，可以转化成求这
两个树的相似度，这又有2个问题，如何做树的查找，如何计算相似。不知大家有没有
做过这方面研究的
它的一个简化版本就是这题 |
|
i**********e
发帖数: 1145 | 50 Print Edge Nodes (Boundary) of a Binary Tree
问题是要把树的周围counter-clockwise打印出来。先打印root，然后从上到下打印最
左边的节点，然后从左到右的顺序打印叶子节点，然后从下到上打印最右边的节点。这
题的精粹就在于使用depth-first traversal，一个递归就能搞定。先把树分为两个树
（root的左孩子和右孩子）处理。先处理左树，再处理右树。如果卡在怎么从下到上打
印最右边节点，可以想想post-order traversal。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
