LeetCode.543.Diameter of Binary Tree 二叉树的直径

题目描述

543 Diameter of Binary Tree
https://leetcode.com/problems/diameter-of-binary-tree/description/
https://leetcode-cn.com/problems/diameter-of-binary-tree/

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:
Given a binary tree

         1
        / \
       2   3
      / \
     4   5

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.

---

相似题目

LeetCode.687.Longest Univalue Path 二叉树的最长同值路径
LeetCode.543.Diameter of Binary Tree 二叉树的直径
LeetCode.124.Binary Tree Maximum Path Sum 二叉树的最大路径和

---

解题过程

解题过程V2018

一直就很害怕做树和图的题，太难了。在做了十几道简单LeetCode后，终于开始尝试做一道二叉树的题。为此专门复习了一下二叉树，下载了严蔚敏版的《数据结构》pdf。

求二叉树的直径，从来没遇见过，第一想法就是根结点的左子树深度加右子树深度，虽然题干中提示了路径不一定经过根结点，但感觉要想路径最长，肯定得过根结点才行。
第一版的代码如下：

class Solution {
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null)
            return 0;
        else
            return treeDepth(root.left) + treeDepth(root.right);//左子树深度+右子树深度
    }

    //递归计算二叉树的深度
    private int treeDepth(TreeNode root){
        if(root == null){
            return 0;
        }else{
            int rightDepth = treeDepth(root.right);
            int leftDepth = treeDepth(root.left);
            return rightDepth>leftDepth ? rightDepth+1 : leftDepth+1;
        }
    }
}

提交后出来个Wrong Answer，102 / 106 test cases passed.
过不去的测试用例是：
[4,-7,-3,null,null,-9,-3,9,-7,-4,null,6,null,-6,-6,null,null,0,6,5,null,9,null,null,-1,-4,null,null,null,-2]
如图

LeetCode的树可视化功能

认真看了看不通过测试用例的可视化图，发现以-9结点为根的子树的直径是8，看来我的思路是错的，最长路径不一定经过根结点，然后把代码改了改，递归的对左右子树算一下其左右子树深度之和，并与当前结点的左右子树深度之和比较，取较大者。

class Solution {
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null)
            return 0;
        else{
            int sumDepth = treeDepth(root.left) + treeDepth(root.right);//左右子树深度之和
            int leftSumDepth = diameterOfBinaryTree(root.left);//左子树的左右子树深度之和
            int rightSumDepth = diameterOfBinaryTree(root.right);//右子树的左右子树深度之和
            return Math.max(sumDepth, Math.max(leftSumDepth, rightSumDepth));//取较大者
        }
    }

    //递归计算二叉树的深度
    private int treeDepth(TreeNode root){
        if(root == null){
            return 0;
        }else{
            int rightDepth = treeDepth(root.right);
            int leftDepth = treeDepth(root.left);
            return rightDepth>leftDepth ? rightDepth+1 : leftDepth+1;
        }
    }
}

代码性能肯定是不行的，一有递归时间复杂度就高，更别说递归里面套递归，结果只打败了2.4%的代码。

然后看别人的代码，发现我的代码太繁琐了，大部分都是用一个全局变量来记录遍历过程中得到的最大左右子树深度之和，如下：

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;
    }
}

速度最快的也是这种方法。相比来说，我的代码整整多了一层循环，太低效了，用一个全局变量在求每个结点深度的过程中直接就能得出结果。

最后总结一下，这道题的思路是：经过每个结点的最长路径就是此结点的左右子树深度之和，但整个树的最长路径（也就是树的直径）并不一定经过根结点，所以要遍历所有结点，依次求其左右子树深度之和，记录下最大值就是树的直径。而求最大值的过程在计算树的深度过程中即可完成。

---

解题过程V2020

2020年第二遍做这个题，上来直接写出来的就是最优方法，看来做题的确不白做。
递归求二叉树的深度，计算过程中更新全局变量diameter，也就是左右子树深度之和的最大值，就是直径。
时间复杂度 O(n) ，空间复杂度 O(n)

private static class SolutionV2020 {
    private int diameter = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        diameter = 0;
        depth(root);
        return diameter;
    }

    // 递归计算树深度，计算过程中更新树的直径（左右子树深度之和的最大值）
    private int depth(TreeNode root) {
        if (null == root) {
            return 0;
        }
        int left = depth(root.left);
        int right = depth(root.right);
        diameter = Math.max(diameter, left + right);
        return Math.max(left, right) + 1;
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_543_DiameterOfBinaryTree.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_543_DiameterOfBinaryTree.java

---