version at 2022-04-20

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

/**
1. 递归统计当前树左右子树的深度 和以当前节点为中继的直径长度即可, 所有节点直径的最大值为所求
*/
class Solution {
    public int diameterOfBinaryTree(TreeNode root) {
        int[] result = new int[1];

        maxPathLength(root, result);

        return result[0]-1;
    }

    public int maxPathLength(TreeNode root, int[] result) {
        if (root == null) return 0;

        int left = maxPathLength(root.left, result);
        int right = maxPathLength(root.right, result);

        result[0] = Math.max(result[0], 1 + left + right);

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

/*
1. 二叉树的当前根的直径 =  左子树的深度 + 右子树的深度 
2. 两点直接最长路径不一定经过 root ，需要对所有子树根的结果取 MAX
3. dfs 顺序：当前节点深度 = max(left, right)
4. dfs 状态：目标节点
5. testcase : 
root：null， 随机值
左子树：空，1， 2， 3
左子树：空， 1， 2， 3
左子树的左右子树都特别长，右子树很短

*/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int res = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        return root == null ? 0 : Math.max(getDepth(root.left) + getDepth(root.right), res);
    }

    public int getDepth(TreeNode root){
        if (root == null) return 0;
        int left = getDepth(root.left);
        int right = getDepth(root.right);
        res = Math.max(res, left + right);
        return 1 + Math.max(left, right);
    }
}