i*********h
发帖数: 49 | 1 感谢以下文章的作者：
二叉树是面试中的常考题目。而且许多别的题是基于二叉树的，所以我们必须对二叉树
无比熟悉。
经过多日的努力，以下所有的题目主页君全部实现了一次，并且加上自己的理解，所有
的算法都基本最优化过，并且递归非递归都实现了一次。敬请大家指正：
以下是目录，以及主页君的代码
http://weibo.com/3948019741/Bq8XobZFD
1. 求二叉树中的节点个数:
getNodeNumRec（递归），getNodeNum（迭代）
2. 求二叉树的深度:
getDepthRec（递归），getDepth
3. 前序遍历，中序遍历，后序遍历:
preorderTraversalRec, preorderTraversal, inorderTraversalRec,
postorderTraversalRec
4. 分层遍历二叉树（按层次从上往下，从左往右）:
levelTraversal, levelTraversalRec（递归解法）
5. 将二叉查找树变为有序的双向链表:
conve... 阅读全帖 |
|
j**l
发帖数: 2911 | 2 如何序列化一棵常规二叉树(不一定是BST)
方法一：
先序（中序或者后序）遍历这棵二叉树，对于空的左右孩子，也要输出空格或者某种特
殊字符作为delimiter，输出的序列就是序列化的结果
例如先序遍历输出
ABC@@DE@G@@F@@@
其中@表示空格字符
然后可以用递归的方式按先序（中序或者后序）序列建立二叉树（反序列化）
PROC crt_bt_pre(VAR bt:bitreptr)
read a char from the sequence, store it in ch;
IF ch = ' ' THEN bt: = NIL
ELSE [
new(bt);
bt^.data = ch;
crt_bt_pre(bt^.lchild);
crt_bt_pre(bt^.rchild)
]
ENDP
方法二：
利用如下原理
1) 已知一棵二叉树的先序序列和中序序列，可以唯一地重构这棵二叉树
2) 已知一棵二叉树的中序序列和后序序列，可以唯一的重构这棵二叉树
这样就可以输出先序和中序序列（或者中序和后序序列）作为序列化的结果
如果问起如何重构，比如知道先序序列和中序序列，则
从先序序 |
|
Z**********4
发帖数: 528 | 3 因为做leetcode上面isBalancedTree那题想到的。
本来就打算用Crackcode上面的解法去做
bool isBalancedTree(TreeNode* root){
if(!root) return true;
return (getMaxDepth(root) - getMinDepth(root)) < 2;
}
int getMaxDepth(TreeNode* root){
if(!root)return 0;
return std::max(getMaxDepth(root->left), getMaxDepth(root->right)) + 1;
}
int getMinDepth(TreeNode* root){
if(!root)return 0;
return std::min(getMinDepth(root->left), getMinDepth(root->right)) + 1;
}
可是发现有些case通不过。
比如
1
2 ... 阅读全帖 |
|
z****s
发帖数: 409 | 4 dfs(左子树)；//k=左子树深度。
if (左子树是满二叉树) {
dfs(右子树）；
return 右子树是否是深度为k-1的满二叉树，或深度为k的完全二叉树；
} esle if (左子树不是满二叉树，但是完全二叉树） {
dfs(右子树）；
return 右子树是否是深度为k-1的满二叉树；
} else return false；
包子拿来吧。 |
|
i****1
发帖数: 445 | 5 以前国内学的时候分为：满二叉树，完全二叉树。
但是最近发现还有一种二叉树，所有节点要么度为2， 要么为0，没有度为1的节点，这
种树应该是哈夫曼编码树
面试的时候说英文就不好判断了。
如满二叉树full binary tree
完全二叉树complete binary tree
不过我看到一些试题说full binary tree是哈夫曼树。
概念混淆，是不是我理解错了？ |
|
K*********n
发帖数: 2852 | 6 是一般意义的二叉树，不是二叉搜索树(BST)。
对于BST，如果待删节点有两个孩子，那么就可以把左子树最右的叶子结点或者右子树最
左的叶子结点搞上来取代删掉的结点，这样保持BST的性质不变。
假如是个普通的二叉树，怎么办呢……网上找了半天都是BST的，CLRS里面说的也是BST
。
我想，一个最简单的办法就是随便找一个叶子结点，来取代删掉的结点就可以了，因为
一般二叉树没有说有什么性质的限定，所以就不care了。一般是不是没有给定树的性质
的限定，不必在乎这种一般的二叉树的删除问题？ |
|
t****o
发帖数: 31 | 7 1.二叉树->binary tree BST->二叉搜索树
2.就是把二叉树变成一个sequence,这个sequence需要和二叉树一一对应并能根据它重
建二叉树 |
|
r***6
发帖数: 15 | 8 题目就是如何serialize二叉树使其便于网上传输。我说可以用中序和先序遍历把二叉
树的结构保存下来。然后再传输遍历后的中序和先序数组。
但面试的人说如果二叉树中有重复元素该算法在重建二叉树的时候会出错，想想也是。
那么到底用什么方法能实现有重复元素的二叉树串行化呢？ |
|
L*********g
发帖数: 8 | 9 先是问了一些概念题，然后还剩30分钟：写个函数判断二叉树是完全二叉树
complete tree
例如
是：
a
/
b c
/ /
d e f g
/
h i
是：
a
/
b c
/ /
d e f g
/ /
h ij
不是：
a
/
b c
/ /
d e f g
/
h i j
不是：
a
/
b c
/
d e g
/
h i
只记得完全二叉树用在堆排序中。吭哧半天，想出了个算法能实现：只能按层遍历（看
下面的三步）。但到最后没时间了，代码没写... 阅读全帖 |
|
j**l
发帖数: 2911 | 10 嗯，你这个其实就是顺序存储结构，即用三个数组来存储一棵二叉树。也可以把data，
left, right放在同一个struct里头，这样只需要一个数组，每个元素是包含三个域(
data, left, right)的struct。
另外，如果是完全二叉树，连left, right都可以省略掉，因为可以推算出来，比如0号
元素的左孩子是1，右孩子是2, i号元素的左孩子是2*i+1, 右孩子是2*i+2，如果值大
于结点个数，则该孩子不存在。普通二叉树也可以用这种完全二叉树的存储方式，但必
须标志某些结点是空的，这会造成空间的浪费。最坏情况是右单支树，一棵高度为k的
右单支树，只有k个结点，却需要2^k - 1个数组元素的空间。 |
|
z*******6
发帖数: 45 | 11 感觉你还是要好好提高一下姿势水平。
首先，二叉树是一种数据结构，与语言本身无关，与算法也没有直接关系。
其次，二叉树只是树型结构中最基本的一种，其扩展还有二叉平衡术，红黑树，B树等
等，这些数据结构广泛用于文件系统，数据库等领域。
另外，关于搜索，无论你用什么语言，你都可以选择高效算法，也都可以选择低效算法
。你所说的其他语言没有用，可能性有两个：第一，你没有用；第二，你没有显示的用
，但是事实上你所用的函数已经帮你完成了这些工作。比如你用python里面的map来存
储和搜索，你自己没有显示的用到任何树结构，但是python内部在实现的时候有可能就
是用了某些树的结构。这一点在C++也一样。你可以选择自己从头实现，也可以选择直
接使用各类函数。
最后，希望你能继续努力学习C++。语言学习不在数量，在于质量。能够精通一门比泛
泛学习多门语言更有意义，也更见功力。 |
|
x****o
发帖数: 21566 | 12 【 以下文字转载自 WaterWorld 讨论区 】
发信人: rabbit8 (兔子), 信区: WaterWorld
标 题: 借人气问问，C++二叉树
发信站: BBS 未名空间站 (Wed Jul 9 11:56:13 2014, 美东)
我在看C++，看到二叉树，谷歌一下，发现是个很基础的东西。对搜索、索引、添加数
据都很有用。
既然这么有用，这么重要，别的语言怎么没有呢？
我以前学过一些别的语言，例如，Basic、PHP、Python、R、MySQL、MATLAB、FORTRAN
、JAVA Script、、等等，为啥都不要二叉树，照样搜索，照样存储。
C++一定要用二叉树吗？
谢谢各位高人指点。 |
|
i**********e
发帖数: 1145 | 13 【 以下文字转载自 JobHunting 讨论区 】
发信人: ihasleetcode (1337coder), 信区: JobHunting
标 题: 转一些我blog上一些常见的二叉树面试问题和总结
发信站: BBS 未名空间站 (Sat Sep 18 22:32:55 2010, 美东)
二叉树是面试里常见的问题种类，大家在面试前必须熟悉这一类的问题。以下是我收集的一些常见二叉树面试问题（包括我亲身经历的）。多做多练习，相信你一定可以掌握好。
Determine if a Binary Tree is a Binary Search Tree
这题很常见，microsoft,amazon, google的面试都有人被问过。这题也是二叉树的好题
，必须得对BST的定义搞清楚。有一个常见的陷阱，就是把current node的value和left
node, right node比较；这是不正确的解法。也有一个很容易想到的brute force解法
，但是每个node会被遍历很多次。正确的优解是 （O(N)解，N=number of nodes)有两
种，面试者必须对这题熟悉。 |
|
i**********e
发帖数: 1145 | 14 【 以下文字转载自 JobHunting 讨论区 】
发信人: ihasleetcode (1337coder), 信区: JobHunting
标 题: 转一些我blog上一些常见的二叉树面试问题和总结
发信站: BBS 未名空间站 (Sat Sep 18 22:32:55 2010, 美东)
二叉树是面试里常见的问题种类，大家在面试前必须熟悉这一类的问题。以下是我收集的一些常见二叉树面试问题（包括我亲身经历的）。多做多练习，相信你一定可以掌握好。
Determine if a Binary Tree is a Binary Search Tree
这题很常见，microsoft,amazon, google的面试都有人被问过。这题也是二叉树的好题
，必须得对BST的定义搞清楚。有一个常见的陷阱，就是把current node的value和left
node, right node比较；这是不正确的解法。也有一个很容易想到的brute force解法
，但是每个node会被遍历很多次。正确的优解是 （O(N)解，N=number of nodes)有两
种，面试者必须对这题熟悉。 |
|
m******n
发帖数: 354 | 15 没有人回啊。
抱歉，可能我没有把问题说清楚。
真诚向大家请教下面的两个问题，不胜感激！
二叉树都是假设股价的binomial distribution来逼近log-normal distribution.
问题一：而B-S formula是时间段无限小的二叉树，即连续形式，是真正的log-normal,
那二叉树还有什么意义呢，实际工作中还会有人用么？
JR (Jarrow-Rudd) -tree 和 CRR (Cox-Ross-Rubinstein) -tree假设的incremental
price change, 也就是up and down multiplier不同，因此相应的tree probabilities
也不同，但当然都是为了要逼近log-normal distribution. (所以也可能存在别的tree
model?)
小弟我试了一下JR和CRR和B-S，发现JR-tree的定价结果要远比CRR-tree的更接近B-S
formula的值。
问题二：为什么大多数的经典书籍，包括被奉为“bible”的john hull那本也都只介绍
CRR-tree呢，难道在实际 |
|
i**********e
发帖数: 1145 | 16 二叉树是面试里常见的问题种类，大家在面试前必须熟悉这一类的问题。以下是我收集的一些常见二叉树面试问题（包括我亲身经历的）。多做多练习，相信你一定可以掌握好。
Determine if a Binary Tree is a Binary Search Tree
这题很常见，microsoft,amazon, google的面试都有人被问过。这题也是二叉树的好题
，必须得对BST的定义搞清楚。有一个常见的陷阱，就是把current node的value和left
node, right node比较；这是不正确的解法。也有一个很容易想到的brute force解法
，但是每个node会被遍历很多次。正确的优解是 （O(N)解，N=number of nodes)有两
种，面试者必须对这题熟悉。
Binary Search Tree In-Order Traversal Iterative Solution
这题应该是 google 电面经常问的问题吧。我那时候就是google电面没答好这问题，所
以就fail了，超级后悔啊。强烈推荐的问题。In-Order traversal能很轻松地用递 |
|
c*********t
发帖数: 2921 | 17 1. 二叉树是不是就是所谓的BST? 中英文我对不起来
2. 看到有人在本版说过“序列化和反序列化二叉树”，二叉树的serialization和
deserialization，这个到底是个什么问题？这个问题的确切描述是什么？
谢谢！ |
|
q****x
发帖数: 7404 | 18 有没有可能inplace？
1. 利用二叉树指针空间，把二叉树转成两个排序双链表。
2. 合并两个链表。
3. 将排序双链表转成二叉树。
不过这样似乎很无聊。时间O(nlogn)空间O(1)，和一个个插入一回事。 |
|
d*******n
发帖数: 263 | 19 二叉树每个节点有个非负整数val，所有节点的val的和等于二叉树节点总数。
现在要把二叉树调整成每个节点的val都是1，每个节点一次可以向自己的相邻节点移动
1，求最少步骤的调整过程。 |
|
r*****8
发帖数: 2560 | 20 我在看C++，看到二叉树，谷歌一下，发现是个很基础的东西。对搜索、索引、添加数
据都很有用。
既然这么有用，这么重要，别的语言怎么没有呢？
我以前学过一些别的语言，例如，Basic、PHP、Python、R、MySQL、MATLAB、FORTRAN
、JAVA Script、、等等，为啥都不要二叉树，照样搜索，照样存储。
C++一定要用二叉树吗？
谢谢各位高人指点。 |
|
r*****8
发帖数: 2560 | 21 不管计算机发展多快，总有更大的计算要求，所以速度和效率都很重要。
但是，比如，R用来算大数据的，也用不着什么二叉树啊。
MySQL，数据库专门用来存储和搜索的，也用不着二叉树。
是不是C++/C太原始了，别的语言里二叉树已经是语言的一部分了。 |
|
s*****n
发帖数: 5488 | 22 如果可以破坏树的结构是可以的，思路是把二叉树，转换为兄弟树。
第一遍转化为兄弟树后，则rightchild指针省下来了，那么值想
p->leftchild->sibling->next = p->next->leftchild, 这样就构成了一张linkedlist
per level.然后for level, print linkedlist.
我估计最后兄弟树还可以恢复为二叉树。
不过这个方法算是很闲的蛋疼了。 |
|
l****r
发帖数: 105 | 23 最近没事刷刷leetcode，碰到几个二叉树问题，测试时创建二叉树手写起来太麻烦（C#
），所以想自己搞个工具，作用是根据给定数组创建二叉树。
初步写出来是这样的：
public static TreeNode CreateBinaryTree(int[] values)
{
TreeNode root = new TreeNode(values[0]);
Queue nodeQueue = new Queue();
nodeQueue.Enqueue(root);
TreeNode current = null;
foreach (var value in values.Skip(1))
{
if (current == null || (current.left != null && current.
right != null))
... 阅读全帖 |
|
r****o
发帖数: 1950 | 24 非递归求二叉树的高度，可以用按层次遍历的方法，层数就是高度。
还有其他方法可以非递归求二叉树高度吗? |
|
l*********8
发帖数: 4642 | 25 这个方法类似二叉树遍历， 二叉树遍历也有路径回溯，但还是O(n)的算法。 |
|
b******g
发帖数: 3616 | 26 感谢分享。不少是Leetcode的题。
我个人最近几次面试的体会是这些还不够。恰恰经常被考到的是二叉树最最基本却又不
那么简单的一些操作。比如如何在平衡二叉树中插入元素并仍旧保持平衡，这种算法书
上最基本的概念，往往是我们刷题的时候会遗漏掉的。 |
|
z*******o
发帖数: 4773 | 27 海关问二叉树，
你得把他忽悠的拿大顶，拿两腿比二叉树 |
|
G***n
发帖数: 877 | 28 二叉树是数据结构，很多语言library的container很多都是二叉树的结构，比如c++里
STL的Map，所以你要知道这个。
FORTRAN |
|
M*P
发帖数: 6456 | 29 二叉树显然是C++的核心
C++里面的++就是二叉树的意思。
★ 发自iPhone App: ChineseWeb 7.8 |
|
c*********e
发帖数: 16335 | 30 如果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 | 31 非常好的计算机算法内容博客，
多谢分享
集的一些常见二叉树面试问题（包括我亲身经历的）。多做多练习，相信你一定可以掌
握好。我会在这里更新和添加常见到的二叉树问题。
left |
|
v*****t
发帖数: 127 | 32 其实一个二叉树就是一个
2*N的矩阵就能表示它的结构
同样的道理，k叉树用k*N的矩阵
一个图用N*N的矩阵
这样带着用矩阵表示结构的思想去考虑，这类的serilize问题，以及做deep copy的问
题，就迎刃而解了。 |
|
z**z
发帖数: 222 | 33 二叉树的情况，左子树 inorder: node->left, node, node->right
右子树 inorder: node->right, node, node->left
这两个子树遍历相等就可以了吧
如果是N叉树的情况，正常遍历用level用queue比较简单，
判断对称有什么思路吗?? |
|
K*****k
发帖数: 430 | 34 定义直径为连通两节点最多的边数
空树和单节点树的直径都是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 | 35 给定一个inorder和preorder构建一颗二叉树
如果，这里面有duplicated的元素，请问如何做？还是根本做不了？ 因为你无法在
inorder里面判断哪个是左树还是右树啊 |
|
c***g
发帖数: 472 | 36 给定一个inorder和preorder构建一颗二叉树
如果，这里面有duplicated的元素，请问如何做？还是根本做不了？ 因为你无法在
inorder里面判断哪个是左树还是右树啊 |
|
z****e
发帖数: 54598 | 37 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来说，要常用太多 |
|
h*****g
发帖数: 312 | 38 7
/ \
8 9
\ / \
5 4 6
inorder: 857496
BFS: 789645
如何 重构这个二叉树，然后求树的宽度（哪一层node最多？） |
|
g****u
发帖数: 252 | 39 我觉得你的算法是对的. 一个小优化是找两个subarray的分界点可以用二分查找. 但是
在递归过程中必须维护当前子树的值的上下界,一旦越界就报错. 我觉得不值得这么折
腾.
还有一个办法就是反向读数组, 然后重建BST. 每读一个数都应该可以找到二叉树中唯
一插入的位置, 如果找不到的话就报错. 但是找插入位置的过程的复杂度至少是树的高
度,也就是O(log N), 所以总体还是O(N logN), 实现的复杂度就差多了. |
|
j***a
发帖数: 1100 | 40 平衡二叉树有很多种方法吧。
最简单的应该是avl 树。 |
|
|
g*******y
发帖数: 1930 | 42 对的。
这个方法是我以前做一道完全二叉树/DFS的时候的方法，昨天面挂了过度沮丧，今天就头晕了随口说了。。。 |
|
r****o
发帖数: 1950 | 43 用书上通用的用queue的方法实现二叉树按层次打印，结果全打印到一行了。
不知道有没有什么好办法可以插入换行符，让每层数据在不同的行显示？ |
|
c******f
发帖数: 2144 | 44 这个应该等价二叉树的遍历
那么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 | 45 不错，正在复习这一块。。
谢谢分享和总结。。
集的一些常见二叉树面试问题（包括我亲身经历的）。多做多练习，相信你一定可以掌
握好。
left |
|
s*******t
发帖数: 248 | 46 常看楼主博客，收获很大，谢谢！
集的一些常见二叉树面试问题（包括我亲身经历的）。多做多练习，相信你一定可以掌
握好。
left |
|
h******3
发帖数: 351 | 47 请问能否share
Binary Search Tree In Order Iterative Traversal without using a visited flag
的方法?
集的一些常见二叉树面试问题（包括我亲身经历的）。多做多练习，相信你一定可以掌
握好。
left |
|
s**a
发帖数: 131 | 48 Thanks.
集的一些常见二叉树面试问题（包括我亲身经历的）。多做多练习，相信你一定可以掌
握好。
left |
|
i**********e
发帖数: 1145 | 49 更新：
Finding the Maximum Height of a Binary Tree
这题就是寻找二叉树的最深度，利用DFS可以轻松解决。挑战的是：如何写非递归的版
本。有两种解法，一是用BFS，解法比较直接。另一种解法是转换成非递归BFS，方法请
参考In-Order Traversal Iterative Solution.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
t*****j
发帖数: 1105 | 50 对于遍历二叉树的复杂度，一直有疑问。
先根遍历应该是O(n)吧，中根和后根呢？ |
|
