LeetCode Weekly Contest 24 之 543. Diameter of Binary Tree

LeetCode Weekly Contest 24

赛题

本次周赛主要分为一下4道题：

• 543 Diameter of Binary Tree (4分)
• 538 Convert BST to Greater Tree (6分)
• 542 01 Matrix (7分)
• 544 Output Contest Matches (7分)

543 Diameter of Binary Tree

Problem:

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:

alt text

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note

The length of path between two nodes is represented by the number of edges between them.

一道典型的DFS，没有什么好说的，直接上我的解决方案。

My first solution(27ms)

public int diameterOfBinaryTree(TreeNode root) {

        if(root == null) return 0;

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

        return Math.max(Math.max(diameterOfBinaryTree(root.left), diameterOfBinaryTree(root.right)), left + right);
    }

    private int maxDepth(TreeNode root){

        if(root == null) return 0;

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

        return left > right ? 1+left : 1+right;
    }

第一反映是递归，假设root的左子树以及右子树的diameterOfBinaryTree已经求解出来，那么我们只需要判断一种情况即可，即diameterOfBinaryTree的path并没有经过根节点的情况。

也就是说，path存在于root的左子树或者右子树中。遇到这种情况，只有可能是左子树的深度+右子树的深度 < 左子树的diameter或者右子树的diameter。所以就有了在递归中left+right，取三种情况的最大值就好了。

当然，在这里我们还可以看一种更加简洁的方法，不必像我的方案一样，多了一堆重复的东西（太含糊了，可以从性能的角度来定量分析）。怎么优化呢？在上述解决方案中，我们是让树的深度和直径分别递归，而直径的解其实可以在求树的深度时不断更新的。因为在最基础的情况，如：[1,2,3]，1的左节点为2，右节点为3的情况下，diameter = left + right = 1 + 1 = 2.，这是优化的关键，也就有了我们下面的解决方案。

My second solution(10ms)

我们来模拟该方案的实现过程。首先，我们首要目标还是求解树的深度，所以，有如下代码。

private int maxDepth(TreeNode root) {
        if (root == null) return 0;

        int left = maxDepth(root.left);
        int right = maxDepth(root.right);     
        return Math.max(left, right) + 1;
    }

经典的求解树的深度code，好了，刚才说了，我们需要把diameter嵌入到maxDepth()中去，最基本的情形是diameter = left + right = 2吧，想想[1,2,3]。而随着递归到底后，归纳向上组装解的时候，一旦有新的left+right 大于原先的diameter，就应该更新。所以也就有了， int max = Math.max(max,left+right)

所以进一步的，代码就更新为我们的完整版解决方案，如下。

public class Solution {
    int max = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        maxDepth(root);
        return max;
    }

    private int maxDepth(TreeNode root) {
        if (root == null) return 0;

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

        max = Math.max(max, left + right);

        return Math.max(left, right) + 1;
    }
}

实际的运行效果也比我原先的代码要好得多且简洁很多。