543. 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

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

[暴力解法]：

时间分析：

空间分析：

［奇葩输出条件］：

［奇葩corner case］：

［思维问题］：

以为helper的参数是左右两个点。结果是求深度的helper函数参数只有一个点：表示求一个点的最大深度，从简单做起。

［一句话思路］：

求一个点的最大深度，从简单做起。

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

两条线段拼接时深度不用加一，单点的深度要加一。稍微注意下

［一刷］：

［二刷］：

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

［总结］：

两条线段拼接时深度不用加一，单点的深度要加一。

［复杂度］：Time complexity: O(n) Space complexity: O(n)

［英文数据结构或算法，为什么不用别的数据结构或算法］：

［关键模板化代码］：

求深度的参数只有一个点：

//define left, right
        int left = depth(root.left);
        int right = depth(root.right);

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

[代码风格] ：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int max = 0;
    
    public int diameterOfBinaryTree(TreeNode root) {
        //corner case
        if (root == null) {
            return 0;
        }
        //depth
        depth(root);
        //return max;
        return max;
    }
    
    public int depth(TreeNode root) {
        //corner case
        if (root == null) {
            return 0;
        }
        //define left, right
        int left = depth(root.left);
        int right = depth(root.right);
        //renew max, don't add 1 since it's a sum of two lines
        max = Math.max(max, left + right);
        //return val for root
        return Math.max(left, right) + 1;
    }
}

View Code