Given the root of a binary tree, return 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.

The length of a path between two nodes is represented by the number of edges between them. ->找diameter：為兩個節點中的最長路徑

Example 1:

Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

Example 2:

Input: root = [1,2]
Output: 1

<解題>

1. 用calculateHeight來計算root的高度及最大直徑值。
2. 在calculateHeight中，先分別用遞迴計算左節點高度、右節點高度
3. 接著，更新最大直徑：Math.max(目前最大直徑,左右高度相加)
4. 接著，返回節點的高度
5. 最後，將答案最大直徑maxDiameter返回

class Solution {
    private int maxDiameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        calculateHeight(root);
        return maxDiameter;
    }

    private int calculateHeight(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftHeight = calculateHeight(node.left);
        int rightHeight = calculateHeight(node.right);

        // 更新最大直徑
        maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);

        // 返回節點的高度
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

Time：O(N) Space：O(H)(樹的高度)