[LeetCode 687]最长同值路径

题目描述

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

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

示例1

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

示例2

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

提示

• 树的节点数的范围是 [0, 104]
• -1000 <= Node.val <= 1000
• 树的深度将不超过 1000

思路分析

1.dfs的返回值是什么？

如图，对于根节点而言，需要求的是
a.左子树单侧最长路径，也就是max(L1,R1)
b.右子树单侧最长路径，也就是max(L2,R2)
c.所以根据以上描述，dfs返回的应该是当前节点单侧最长路径长度，对于上图来说，左孩子返回的是max(L1,R1) + 1，右孩子返回的是max(L2,R2) + 1
d.如果孩子和根节点的值不同，则返回0！

2.对于每个节点如何求以当前节点的最长路径？
L + R就是要求的路径长度

3.将上述两个逻辑分析清楚之后，代码就好写了

代码：

class Solution {
public:
    int res = 0;
    int dfs(TreeNode* root){
        if(!root) return 0;
        int l = dfs(root->left), r = dfs(root->right);
        //如果孩子节点的值与父节点值不一样，说明延伸不出去，长度为0
        if(!root->left || root->val != root->left->val) l = 0;
        if(!root->right || root->val != root->right->val) r = 0;
        //计算以当前节点为根节点的最长同值路径
        res = max(res, l + r);
        //返回值是单侧的路径长度+1
        return max(l, r) + 1;
    }
    int longestUnivaluePath(TreeNode* root) {
        if(!root) return 0;
        dfs(root);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20