s**a
发帖数: 131 | 1 Thanks.
集的一些常见二叉树面试问题（包括我亲身经历的）。多做多练习，相信你一定可以掌
握好。
left |
|
i**********e
发帖数: 1145 | 2 更新：
Finding the Maximum Height of a Binary Tree
这题就是寻找二叉树的最深度，利用DFS可以轻松解决。挑战的是：如何写非递归的版
本。有两种解法，一是用BFS，解法比较直接。另一种解法是转换成非递归BFS，方法请
参考In-Order Traversal Iterative Solution.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
t*****j
发帖数: 1105 | 3 对于遍历二叉树的复杂度，一直有疑问。
先根遍历应该是O(n)吧，中根和后根呢？ |
|
i******t
发帖数: 158 | 4 还是按楼主的方法,加上dummy node, 变成完全二叉树, 就可以了 |
|
K*****k
发帖数: 430 | 5 定义直径为连通两节点最多的边数
空树和单节点树的直径都是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***g
发帖数: 472 | 7 给定一个inorder和preorder构建一颗二叉树
如果，这里面有duplicated的元素，请问如何做？还是根本做不了？ 因为你无法在
inorder里面判断哪个是左树还是右树啊 |
|
L***Q
发帖数: 508 | 8 如果有duplicate，应该是无法唯一确定。一个三个node的例子：3 3 3.前序中序都这
结果，可以有好几种二叉树。 |
|
c***g
发帖数: 472 | 9 给定一个inorder和preorder构建一颗二叉树
如果，这里面有duplicated的元素，请问如何做？还是根本做不了？ 因为你无法在
inorder里面判断哪个是左树还是右树啊 |
|
L***Q
发帖数: 508 | 10 如果有duplicate，应该是无法唯一确定。一个三个node的例子：3 3 3.前序中序都这
结果，可以有好几种二叉树。 |
|
h*****g
发帖数: 312 | 11 7
/ \
8 9
\ / \
5 4 6
inorder: 857496
BFS: 789645
如何 重构这个二叉树，然后求树的宽度（哪一层node最多？） |
|
|
|
p********n
发帖数: 20 | 14 对二叉树进行DFS，将遍历过程中遇到的节点按顺序记下，得到一个长度为2N-1的节点
序列，就是欧拉序列。 |
|
K*********n
发帖数: 2852 | 15 就是，不会考这种问题是吧。好久不复习数据结构，今天写一个非BST的二叉树，写着写
着就遇到这个问题了，手生，莫笑哈。 |
|
c********t
发帖数: 5706 | 16 响应号召，发中文题
二叉树求两结点间最大路径问题已经有很好解法。
现在有一个变体题，两点间最大路径必须要加上共同祖先到root这段。
比如：
3
/
4
/ \
1 2
结果为10
请问有什么好的解法？
我有一个笨解法，指数时间复杂度，为了不影响大家做题，会在跟帖贴出。 |
|
r*****e
发帖数: 146 | 17 二叉查找树中两个节点被错误的交换了，如何有效找出他们。有没有比较neat的解法？
谢谢 |
|
h****n
发帖数: 1093 | 18 inorder travese即可找第一个不对路和最后一个不对路的交换即可
二叉查找树中两个节点被错误的交换了，如何有效找出他们。有没有比较neat的解法？
谢谢
★ Sent from iPhone App: iReader Mitbbs Lite 7.56 |
|
|
g****y
发帖数: 240 | 20 是给一个值找一个节点，还是说随机返回二叉树中的一个节点？ |
|
g****u
发帖数: 252 | 21 我觉得你的算法是对的. 一个小优化是找两个subarray的分界点可以用二分查找. 但是
在递归过程中必须维护当前子树的值的上下界,一旦越界就报错. 我觉得不值得这么折
腾.
还有一个办法就是反向读数组, 然后重建BST. 每读一个数都应该可以找到二叉树中唯
一插入的位置, 如果找不到的话就报错. 但是找插入位置的过程的复杂度至少是树的高
度,也就是O(log N), 所以总体还是O(N logN), 实现的复杂度就差多了. |
|
r**h
发帖数: 1288 | 22 我猜lz想问的是二叉树使用stack/循环的pre-order traversal的实现？ |
|
x********9
发帖数: 7 | 23 要求要数组 实现二叉树 and implement following methods:
set(K, V)
get(K)
求教各位高手 |
|
|
|
|
p**t
发帖数: 157 | 27 不会用栈遍历二叉树的 你让他用栈做DFS不是更不会。。。 |
|
|
j***a
发帖数: 1100 | 29 平衡二叉树有很多种方法吧。
最简单的应该是avl 树。 |
|
d**********1
发帖数: 569 | 30 有，但是实现起来效率不高且麻烦。
C/C++的优点之一就是运行的速度和算法效率，所以有相当一部分人用C++就是为了算法
和速度，用算法的人多了，所以愿意讨论和实现的人就多了。
Basic PHP Python ...的和C++比起来，特点是入门容易，开发速度快，管理起来（相
对）简单。所以同时要用到这些语言和二叉树检索的机会太少了，用的少，基本也就没
人讨论了。
FORTRAN |
|
|
z*****a
发帖数: 9790 | 32 二叉树是一种数据结构，理论上任何编程语言都可以实现，只不过c/c++的指针实现起
来效率高
FORTRAN |
|
c****p
发帖数: 6474 | 33 你说的应该是二叉搜索树BST。
有些数据结构的底层实现实际上是用BST及其变种实现的，你没有直观地看到BST而已。
就我所知，C++里面的set是用红黑树（平衡BST）实现的。
FORTRAN |
|
