【DFS, 二叉树】最长同值路径

题目

687. 最长同值路径

---

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

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

示例 1:

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

示例 2:

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

提示:

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

解题

方法一：DFS

思路

这题与 【DFS, 二叉树】二叉树中的最大路径和 类似，需要借助中间节点然后递归求出左右子节点的贡献值，根据贡献值求出经过该节点的最长同值路径，维护一个最长同值路径。

这题的贡献值定义是：规定一个节点的贡献值为在以它为根节点的子树中以该节点为起点的一条同值路径最长的路径的长度，例如：

那么经过某一节点的最长同值路径就是左右子节点贡献值之和，例如图中求经过节点4的最长同值路径就是 $1 + 1 = 2$。

那么开始递归，传入一个节点(node)和它的父节点的值(val)：

• 如果该节点为空，返回贡献值 0。
• 递归地求出其左右子节点的贡献值。
• 维护最长同值路径(maxLen)。
• 如果该节点值与其父节点值(val)相同说明可以连成同值路径，返回该节点的贡献值(该节点值加上左右子节点贡献值中较大的一个)加一，否则说明不能连成同值路径，该节点的贡献值再高也没用，返回 0。

代码

class Solution {
    int maxLen = 0;

    public int longestUnivaluePath(TreeNode root) {
        if (root == null) return 0;
        dfs(root, root.val);
        return maxLen;
    }

    int dfs(TreeNode node, int val) {
        if (node == null) return 0;
        int left = dfs(node.left, node.val);
        int right = dfs(node.right, node.val);
        maxLen = Math.max(maxLen, left + right);
        if (node.val == val) return Math.max(left, right) + 1;
        return 0;
    }
}

class Solution {
    int max_len = 0;

    int dfs(TreeNode* node, int val) {
        if (!node) return 0;
        int left = dfs(node->left, node->val);
        int right = dfs(node->right, node->val);
        max_len = max(max_len, left + right);
        return node->val == val ? max(left, right) + 1 : 0;
    }

public:
    int longestUnivaluePath(TreeNode* root) {
        if (!root) return 0;
        dfs(root, root->val);
        return max_len;
    }
};