贪心法+DFS求二叉树的直径

遍历每一个节点，以每一个节点为中心点计算最长路径（左子树边长+右子树边长），更新全局变量max。

class Solution {
    int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null)
            return 0;
        maxDepth(root);
        return max;
    }

    public int maxDepth(TreeNode root){
        if(root.left == null && root.right == null)
            return 0;
        int left = root.left == null ? 0 : maxDepth(root.left) + 1;
        int right = root.right == null ? 0 : maxDepth(root.right) + 1;
        max = Math.max(max, left + right);
        return Math.max(left, right);
    }
}

这道题在上面那道题的基础上，添加条件即可。

class Solution {
    int max = 0;
    public int longestUnivaluePath(TreeNode root) {
        if(root == null)
            return 0;
        dfs(root);
        return max;
    }

    public int dfs(TreeNode root){
        if(root.left == null && root.right == null)
            return 0;
        int left = root.left == null ? 0 : dfs(root.left) + 1;
        int right = root.right == null ? 0 : dfs(root.right) + 1;
        if(left > 0 && root.left.val != root.val){
            left = 0;
        }
        if(right > 0 && root.right.val != root.val){
            right = 0;
        }
        max = Math.max(max, left + right);
        return Math.max(left, right);
    }
}