【687. 最长同值路径】

来源：力扣（LeetCode）

描述：

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

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

示例 1:

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

示例 2:

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

提示:

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

方法：深度优先搜索

我们将二叉树看成一个有向图（从父结点指向子结点的边），定义同值有向路径为从某一结点出发，到达它的某一后代节点的路径，且经过的结点的值相同。最长同值路径长度必定为某一节点的左最长同值有向路径长度与右最长同值有向路径长度之和。

使用变量 res 保存最长同值路径长度。我们对根结点进行深度优先搜索，对于当前搜索的结点 root，我们分别获取它左结点的最长同值有向路径长度 left，右结点的最长同值有向路径长度 right。如果结点 root 的左结点非空且结点 root 的值与它的左结点的值相等，那么结点 root 的左最长同值有向路径长度 left₁ = left + 1，否则 left₁ = 0；如果结点 root 的右结点非空且结点 root 的值与它的右结点的值相等，那么结点 root 的右最长同值有向路径长度 right₁ = right + 1，否则 right₁ = 0。令 res = max(res, left₁ + right₁)，并且返回结点 root 对应的最长同值有向路径长度 max(left₁, right₁)。

代码：

class Solution {
private:
    int res;

public:
    int longestUnivaluePath(TreeNode* root) {
        res = 0;
        dfs(root);
        return res;
    }

    int dfs(TreeNode *root) {
        if (root == nullptr) {
            return 0;
        }
        int left = dfs(root->left), right = dfs(root->right);
        int left1 = 0, right1 = 0;
        if (root->left && root->left->val == root->val) {
            left1 = left + 1;
        }
        if (root->right && root->right->val == root->val) {
            right1 = right + 1;
        }
        res = max(res, left1 + right1);
        return max(left1, right1);
    }
};
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

执行用时：116 ms, 在所有 C++ 提交中击败了60.58%的用户
内存消耗：70.1 MB, 在所有 C++ 提交中击败了33.15%的用户
复杂度分析
时间复杂度：O(n)O(n)，其中 nn 为树的结点数目。
空间复杂度：O(n)O(n)。递归栈最坏情况下需要 O(n)O(n) 的空间。
author：LeetCode-Solution