递归法

最长同值路径

给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
注意：两个节点之间的路径长度由它们之间的边数表示。

示例 1:
输入:
              5
             / \
            4   5
           / \   \
          1   1   5
输出:
2  (5->5->5  => 边数为2)

这道题其实可以看成是解决以root为路径起始点的最长路径，这其实就只有两种情况：

(1)第一种是root和左子树（同值）

(2) 第二种是root和右子树（同值）

但是还有种特殊情况，就是左子树-root-右子树（同值），但是这种特殊情况不影响我们递归函数的功能的设计。

int ans = 0;
public int longestUnivaluePath(TreeNode root) {
    longestPath(root);
    return ans;
}

//递归函数功能：搜寻以node为起点的最长同值路径:
//要么是以node为起点的左子树，要么是以node为起点的右子树
private int longestPath(TreeNode node) {
    if (node == null) return 0;
    int maxLorRres = 0;
    TreeNode left = node.left, right = node.right;

    int lval = longestPath(left); //node左子树的最长同值路径
    int rval = longestPath(right); //node右子树的最长同值路径

    //这种情况对于寻找最长同值路径长有帮助，对于搜索以root为路径起始点的最长路径没有帮助
    if (left != null && left.val == node.val && right != null && right.val == node.val) {
        ans = Math.max(ans, lval + rval + 2); //因为求路径(两点之间的边数),所以加2
    }

    //从左右子树中选择最长的同值路径
    if (left != null && left.val == node.val) 
        maxLorRres = Math.max(maxLorRres, lval + 1);
    if (right != null && right.val == node.val) 
        maxLorRres = Math.max(maxLorRres, rval + 1);
    ans = Math.max(ans, maxLorRres);
    
    return maxLorRres;
}

hhhhh