i*********h 发帖数: 49 | 1 感谢以下文章的作者:
二叉树是面试中的常考题目。而且许多别的题是基于二叉树的,所以我们必须对二叉树
无比熟悉。
经过多日的努力,以下所有的题目主页君全部实现了一次,并且加上自己的理解,所有
的算法都基本最优化过,并且递归非递归都实现了一次。敬请大家指正:
以下是目录,以及主页君的代码
http://weibo.com/3948019741/Bq8XobZFD
1. 求二叉树中的节点个数:
getNodeNumRec(递归),getNodeNum(迭代)
2. 求二叉树的深度:
getDepthRec(递归),getDepth
3. 前序遍历,中序遍历,后序遍历:
preorderTraversalRec, preorderTraversal, inorderTraversalRec,
postorderTraversalRec
4. 分层遍历二叉树(按层次从上往下,从左往右):
levelTraversal, levelTraversalRec(递归解法)
5. 将二叉查找树变为有序的双向链表:
convertBST2DLLRec, convertBST2DLL
6. 求二叉树第K层的节点个数:
getNodeNumKthLevelRec, getNodeNumKthLevel
7. 求二叉树中叶子节点的个数:
getNodeNumLeafRec, getNodeNumLeaf
8. 判断两棵二叉树是否相同的树:
isSameRec, isSame
9. 判断二叉树是不是平衡二叉树:isAVLRec
10. 求二叉树的镜像(破坏和不破坏原来的树两种情况):
mirrorRec, mirrorCopyRec
mirror, mirrorCopy
10.1 判断两个树是否互相镜像:isMirrorRec isMirror
11. 求二叉树中两个节点的最低公共祖先节点:
LAC 求解最小公共祖先, 使用list来存储path.
LCABstRec 递归求解BST树.
LCARec 递归算法 .
12. 求二叉树中节点的最大距离:
getMaxDistanceRec
13. 由前序遍历序列和中序遍历序列重建二叉树:
rebuildBinaryTreeRec
14. 判断二叉树是不是完全二叉树:
isCompleteBinaryTree, isCompleteBinaryTreeRec
15. 找出二叉树中最长连续子串(即全部往左的连续节点,或是全部往右的连续节点)
findLongest |
i*********h 发帖数: 49 | |
f*****g 发帖数: 887 | |
f*******w 发帖数: 1243 | |
s********l 发帖数: 998 | |
i*********h 发帖数: 49 | |
l******6 发帖数: 2 | |
a*****s 发帖数: 1121 | |
b******g 发帖数: 3616 | 9 感谢分享。不少是Leetcode的题。
我个人最近几次面试的体会是这些还不够。恰恰经常被考到的是二叉树最最基本却又不
那么简单的一些操作。比如如何在平衡二叉树中插入元素并仍旧保持平衡,这种算法书
上最基本的概念,往往是我们刷题的时候会遗漏掉的。 |
l*****0 发帖数: 118 | 10
说的好!! 很容易遗漏,所以做题时候一定要多多总结,多多思考
【在 b******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 感谢分享。不少是Leetcode的题。 : 我个人最近几次面试的体会是这些还不够。恰恰经常被考到的是二叉树最最基本却又不 : 那么简单的一些操作。比如如何在平衡二叉树中插入元素并仍旧保持平衡,这种算法书 : 上最基本的概念,往往是我们刷题的时候会遗漏掉的。
|
|
|
b******i 发帖数: 914 | 11 感谢,弱问一下,每个题都得既会迭代的又会递归的么?递归的很多时候比较简单
【在 i*********h 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 感谢以下文章的作者: : 二叉树是面试中的常考题目。而且许多别的题是基于二叉树的,所以我们必须对二叉树 : 无比熟悉。 : 经过多日的努力,以下所有的题目主页君全部实现了一次,并且加上自己的理解,所有 : 的算法都基本最优化过,并且递归非递归都实现了一次。敬请大家指正: : 以下是目录,以及主页君的代码 : http://weibo.com/3948019741/Bq8XobZFD : 1. 求二叉树中的节点个数: : getNodeNumRec(递归),getNodeNum(迭代) : 2. 求二叉树的深度:
|
b******i 发帖数: 914 | 12 感谢,请问是否每个题都要既会迭代的又会递归的?
【在 i*********h 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 感谢以下文章的作者: : 二叉树是面试中的常考题目。而且许多别的题是基于二叉树的,所以我们必须对二叉树 : 无比熟悉。 : 经过多日的努力,以下所有的题目主页君全部实现了一次,并且加上自己的理解,所有 : 的算法都基本最优化过,并且递归非递归都实现了一次。敬请大家指正: : 以下是目录,以及主页君的代码 : http://weibo.com/3948019741/Bq8XobZFD : 1. 求二叉树中的节点个数: : getNodeNumRec(递归),getNodeNum(迭代) : 2. 求二叉树的深度:
|
p***y 发帖数: 637 | 13 cc150说不用背平衡二叉树。。看来时代变了
【在 b******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 感谢分享。不少是Leetcode的题。 : 我个人最近几次面试的体会是这些还不够。恰恰经常被考到的是二叉树最最基本却又不 : 那么简单的一些操作。比如如何在平衡二叉树中插入元素并仍旧保持平衡,这种算法书 : 上最基本的概念,往往是我们刷题的时候会遗漏掉的。
|
b******g 发帖数: 3616 | 14 我已经3次面试连续被问到2回了,一口鲜血喷屏幕上
【在 p***y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : cc150说不用背平衡二叉树。。看来时代变了
|
T*****g 发帖数: 1306 | 15 Mark
★ 发自iPhone App: ChineseWeb 8.2.2
【在 i*********h 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 感谢以下文章的作者: : 二叉树是面试中的常考题目。而且许多别的题是基于二叉树的,所以我们必须对二叉树 : 无比熟悉。 : 经过多日的努力,以下所有的题目主页君全部实现了一次,并且加上自己的理解,所有 : 的算法都基本最优化过,并且递归非递归都实现了一次。敬请大家指正: : 以下是目录,以及主页君的代码 : http://weibo.com/3948019741/Bq8XobZFD : 1. 求二叉树中的节点个数: : getNodeNumRec(递归),getNodeNum(迭代) : 2. 求二叉树的深度:
|
i*********h 发帖数: 49 | 16 主要是这样的,有些题目会要求你不可以使用递归,或者是用非递归做起来更简单一些
。所以我们最好都实现一次。
【在 b******i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 感谢,弱问一下,每个题都得既会迭代的又会递归的么?递归的很多时候比较简单
|
i*********h 发帖数: 49 | 17 树的节点删除好像是常常会考的。所以大家还是要加强基本功啊!
另外,链表主页君也总结过一次。回头也发上来。
【在 b******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我已经3次面试连续被问到2回了,一口鲜血喷屏幕上
|
i*********h 发帖数: 49 | 18 请问一下 是什么题目呢?
【在 b******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我已经3次面试连续被问到2回了,一口鲜血喷屏幕上
|
s*******0 发帖数: 23 | |
i*********h 发帖数: 49 | 20 thanks so much.
【在 s*******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : mark and 3xs
|