本文共 1332 字,大约阅读时间需要 4 分钟。
感谢以下文章的作者: BIN大神的大总结: http://blog.csdn.net/fightforyourdream/article/details/16843303 面试大总结之二:Java搞定面试中的二叉树题目 以及: http://blog.csdn.net/luckyxiaoqiang/article/details/7518888 轻松搞定面试中的二叉树题目 http://www.cnblogs.com/Jax/archive/2009/12/28/1633691.html 算法大全(3) 二叉树 二叉树是面试中的常考题目。而且许多别的题是基于二叉树的,所以我们必须对二叉树无比熟悉。 经过多日的努力,以下所有的题目主页君全部实现了一次,并且加上自己的理解,所有的算法都基本最优化过。敬请大家指正: 以下是目录,以及主页君的代码 https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/tree/TreeDemo.java 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