登录
  • #刷题

算法‌‌‍‍‌‍‌‌‌‌‌‌‍‌‌‌‍‍‍‍‍‌‌‍‌‌‌‌‍‌‌‌超级大总结-- 面试中二叉树中常常考的题目欢迎讨论

imabluefish
5965
20
感谢以下文章的作者:

二叉树是面试中的常考题目。而且许多别的题是基于二叉树的,所以我们必须对二叉树

无比熟悉。

经过多日的努力,以下所有的题目主页君全部实现了一次,并且加上自己的理解,所有

的算法都基本最优化过,并且递归非递归都实现了一次。敬请大家指正:

以下是目录,以及主页君的代码

weibo.com

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
20条回复
热度排序

发表回复