687. 最长同值路径 ●●

687. 最长同值路径 ●●

描述

给定一个二叉树的 root ，返回 最长同值路径的长度 ，这个路径中的 每个节点具有相同值 。 这条路径可以经过也可以不经过根节点。

两个节点之间的路径长度 由它们之间的边数表示。

示例

输入：root = [1,4,5,4,4,5]
输出：2

题解

一篇文章解决所有二叉树路径问题（问题分析+分类模板+题目剖析）

DFS (非自顶而下)

这类题目一般解题思路如下：
设计一个辅助函数 maxpath，调用自身求出以一个节点为根节点的左侧最长路径 left 和右侧最长路径 right，那么经过该节点的最长路径就是left + right；接着只需要从根节点开始 dfs，不断比较更新全局变量即可。

int res = 0;
int maxPath(TreeNode *root) //以root为路径起始点的最长路径
{
    if (!root)
        return 0;
    int left = maxPath(root->left);
    int right = maxPath(root->right);
    res = max(res, left + right + root->val); //更新全局变量  
    return max(left, right);   //返回左右路径较长者
}
1
2
3
4
5
6
7
8
9
10

这类题型 DFS 注意点：

1、left，right 代表的含义要根据题目所求设置，比如最长路径、最大路径和等等
2、全局变量 res 的初值设置是 0 还是 INT_MIN 要看题目节点是否存在负值，如果存在就用INT_MIN，否则就是0
3、注意两点之间路径为1，因此一个点是不能构成路径的

• 时间复杂度：O(N)，其中 N 是树中节点数。我们处理每个节点一次。
• 空间复杂度：O(H)，其中 H 是树的高度。我们的递归调用栈可以达到 H 层的深度。

本题代码如下：

class Solution {
public:
    int ans;

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

    int longestPath(TreeNode* node){
        if(node == nullptr) return 0;
        int left = longestPath(node->left);     // 以左孩子为根节点的单边最长长度
        int right = longestPath(node->right);   // 以右孩子为根节点的单边最长长度
        if(node->left != nullptr && node->val == node->left->val){
            ++left;                     // 经过左孩子的单边长度 + 1
        }else{
            left = 0;                   // 不相等则为0 【这里很重要，表示没有路径】
        }
        if(node->right != nullptr && node->val == node->right->val){
            ++right;
        }else{
            right = 0;                  
        }
        ans = max(ans, left + right);   // 更新全局变量，left + right 表示当前节点作为路径根节点
        return max(left, right);        // 返回单边最长长度，当前节点可能不是根节点
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28