687. Longest Univalue Path

Leetcode Tree Depth-first Search

Given a binary tree, find the length of the longest path where each node in the path has the same value. This path may or may not pass through the root.

Note: The length of path between two nodes is represented by the number of edges between them.

Example 1:

Input:

              5
             / \
            4   5
           / \   \
          1   1   5
Output:
2

Example 2:

Input:

              1
             / \
            4   5
           / \   \
          4   4   5
Output:

2

Note: The given binary tree has not more than 10000 nodes. The height of the tree is not more than 1000.

分析

这道题目和LeetCode 124. Binary Tree Maximum Path Sum整体思路是一样的。Q124求的是最大路径和，这道题目求的是最长路径。longestUnivaluePathHelper(root)返回的是从底往上到达root节点的最长路径。maxValue变量保存着最长路径。如果root节点的左子节点和右子节点和root节点的值相同，maxValue要增加，增加的长度和root节点与哪一部分节点相同有关。如果root节点和左右子节点的值都不同，则longestUnivaluePathHelper(root)返回0。

private int maxValue;
public int longestUnivaluePath(TreeNode root) {
    maxValue = 0;
    longestUnivaluePathHelper(root);
    return maxValue;
}

private int longestUnivaluePathHelper(TreeNode root) {
    if (root == null) return 0;
    int left = longestUnivaluePathHelper(root.left);
    int right = longestUnivaluePathHelper(root.right);
    if (root.left != null && root.val == root.left.val) left++;
    else left = 0;
    if (root.right != null && root.val == root.right.val) right++;
    else right = 0;
    maxValue = Math.max(maxValue, left + right);
    return Math.max(left, right);
}