687.最长同值路径

链接：687.最长同值路径
难度：Medium
标签：树、深度优先搜索、二叉树
简介：给定一个二叉树的 root ，返回 最长的路径的长度 ，这个路径中的 每个节点具有相同值 。 这条路径可以经过也可以不经过根节点。

题解 1 - cpp

• 编辑时间：2022-09-02
• 执行用时：84ms
• 内存消耗：49.9MB
• 编程语言：cpp
• 解法介绍：递归,每次记录以根结点起的最长链路和子节点的最长内部链路。

#define MAX(a, b) ((a) > (b) ? (a) : (b))
int longestUnivaluePath(struct TreeNode *root){
    if (!root) return 0;
    int ans = 0;
    _longestUnivaluePath(root, &ans);
    return ans - 1;
}
int _longestUnivaluePath(struct TreeNode *root, int *ans) {
    if (!root) return 0;
    int cnt1 = 1, cnt2 = 1,
        left = _longestUnivaluePath(root->left, ans),
        right = _longestUnivaluePath(root->right, ans);
    if (root->left && root->left->val == root->val) cnt1 = MAX(cnt1, 1 + left), cnt2 += left;
    if (root->right && root->right->val == root->val) cnt1 = MAX(cnt1, 1 + right), cnt2 += right;
    *ans = MAX(*ans, cnt1);
    *ans = MAX(*ans, cnt2);
    return cnt1;
}