2018-03-10 求二叉树直径

二叉树的直径就是任意两点之间的最大距离。图中直径为[4,2,1,3]。

可以看到，图中的树直径为4到3之间的距离，而经过1点的距离才是最长的。

可以将这条最长的路径分为两部分，即[1,2,4] + [1,3]，因此可以将这个问题转化为：求左右子树最大深度之和。

    //遍历所有节点，返回 节点的左右子树最大深度之和 与子节点的左右子树最大深度之和 的最大值

    public int diameterOfBinaryTree(TreeNode root) {

        if (root == null) return 0;

        int maxDepth = depth(root.left) + depth(root.right);

        return max(maxDepth, diameterOfBinaryTree(root.left), diameterOfBinaryTree(root.right));

    }

    //求深度

    public int depth(TreeNode root) {

        if (root == null) return 0;

        return 1 + max(depth(root.left), depth(root.right));

    }

    public int max(int p, int q) {

        return p > q ? p : q;

    }

    public int max(int o, int p, int q) {

        return max(max(o, p), q);

    }