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

感谢以下文章的作者：

二叉树是面试中的常考题目。而且许多别的题是基于二叉树的，所以我们必须对二叉树
无比熟悉。
经过多日的努力，以下所有的题目主页君全部实现了一次，并且加上自己的理解，所有
的算法都基本最优化过，并且递归非递归都实现了一次。敬请大家指正：

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

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

public static int getMaxDistanceRec(TreeNode root) {
        return getMaxDistanceRecHelp(root).maxDistance;
    }
   
    public static Result getMaxDistanceRecHelp(TreeNode root) {
        Result ret = new Result(-1, -1);
        
        if (root == null) {
            return ret;
        }
        
        Result left = getMaxDistanceRecHelp(root.left);
        Result right = getMaxDistanceRecHelp(root.right);
        
        // 深度应加1， the depth from the subtree to the root.
        ret.depth = Math.max(left.depth, right.depth) + 1;
        
        // 左子树，右子树与根的距离都要加1，所以通过根节点的路径为两边深度+2
        int crossLen = left.depth + right.depth + 2;
        
        // 求出cross根的路径，及左右子树的独立路径，这三者路径的最大值。
        ret.maxDistance = Math.max(left.maxDistance, right.maxDistance);
        ret.maxDistance = Math.max(ret.maxDistance, crossLen);
        
        return ret;
    }
我想再问问 maxdistance 是 左右子树的max depth 和 crossLen 进行比较的最大值吗？若如此，为什么需要这个result 的结构呢

public static int getDepthRec(TreeNode root) {
        if (root == null) {
            return -1;
        }
        
        return Math.max(getDepthRec(root.left), getDepthRec(root.right)) + 1;
    }
若为null应该返回0才对吧

imabluefish 发表于 2015-1-9 11:27
null的真实深度就是-1.这是树的定义。你可以查一下算法书。 depth的定义是：从根到最远的叶子节点的边的 ...

谢谢楼主，我发现国内的二叉树和国外的教材定义不同，root的depth的确是0. 国内的是1. 而且我发现我把depth和height也搞混了。非常感谢！

虽然是参考的 但是也是有优化过，比原文章其实更优化

希望大家一起来讨论

imabluefish 发表于 2014-10-22 11:59
希望大家一起来讨论

lz是今年入学的ini学生吗？

marine 发表于 2014-10-23 06:42
lz是今年入学的ini学生吗？

您是？ 加我的qq 私聊吧  我是215573479 我已经2年级了。

顶一顶。

顶一下自己。 谢谢支持

顶一顶。

希望有更多的人看到本帖子。

顶一下帖子。