题解 | #NC195 二叉树的直径#

import java.util.*;

public class Solution {
    public int diameterOfBinaryTree (TreeNode root) {
        // 预处理
        if (root == null) return 0;
        // 获取左子树的最大深度
        int leftDepth = getMaxDepth(root.left);
        // 获取右子树的最大深度
        int rightDepth = getMaxDepth(root.right);

        // 情况1：直径路径过根结点
        int max1 = (leftDepth + 1 + rightDepth) - 1; // 路径长度 = 结点个数 - 1
        // 情况2：直径路径在左子树中
        int max2 = diameterOfBinaryTree(root.left);
        // 情况3：直径路径在右子树中
        int max3 = diameterOfBinaryTree(root.right);

        // 返回三种情况中的最大值
        int[] temp = {max1, max2, max3};
        Arrays.sort(temp);
        return temp[temp.length-1];
    }

    // 获取当前树的最大深度
    public static int getMaxDepth(TreeNode root) {
        // 预处理
        if (root == null) return 0;
        // 递归求左右子树的最大深度
        return Math.max(getMaxDepth(root.left),getMaxDepth(root.right)) + 1;
    }
}