JZX轻语：简

LeetCode 687 - 最长等值路径

发表于2024年04月13日

#树 #递归 #DFS

二叉树DFS的典型用法，其中路径可以绕过根节点连接左右子树中的节点。因此，在遍历到某个节点时, 首先分别在左右子树中寻找值等于该节点的、端点为左右孩子的最长路径(即，路径不会绕过左/右孩子去到另一边)，然后拼接起来作为绕过当前节点的最长路径, 并更新最优解；最后，如果当前节点的值等于父节点的值，则返回以该节点作为端点的最长路径形成递归即可(从左右子树中选择一个较长的路径并加上该节点)；否则，返回0。

class Solution:
    def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:
        rslt = 0

        def dfs(node: Optional[TreeNode], parent_val: int) -> int:
            """ 返回的是从node出发(并不是经过，而是路径的一端一定要是node), 各值均为parent_val的节点数 """
            nonlocal rslt
            if node is None:
                return 0

            l_val = dfs(node.left, node.val)
            r_val = dfs(node.right, node.val)
            # 拼接
            rslt = max(rslt, l_val + r_val + 1)
            if node.val == parent_val:
                # 如果node的值刚好为父节点的值, 则从左/右子树中选择最长的链条长度
                return 1 + max(l_val, r_val)
            return 0
    
        dfs(root, -1001)
        return max(rslt - 1, 0)

闪念标签：LC

题目链接：https://leetcode.cn/problems/longest-univalue-path/description/