【LeetCode】687. 最长同值路径

题目

687. 最长同值路径

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

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

示例 1:

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

示例 2:

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

提示:

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

思路

• 动态规划，$dp[node]$表示以node为根，左右子树中最长相同路径长度，则
  d p [ n o d e ] = { 0 n o d e . l e f t . v a l ≠ n o d e . v a l ∧ n o d e . r i g h t . v a l ≠ n o d e . v a l d p [ n o d e . l e f t ] + 1 n o d e . v a l = n o d e . l e f t . v a l ∧ n o d e . v a l ≠ n o d e . r i g h t . v a l d p [ n o d e . r i g h t ] + 1 n o d e . v a l = n o d e . r i g h t . v a l ∧ n o d e . v a l ≠ n o d e . l e f t . v a l max ⁡ ( d p [ n o d e . l e f t ] + 1 , d p [ n o d e . r i g h t ] + 1 ) n o d e . l e f t . v a l = n o d e . r i g h t . v a l = n o d e . v a l dp[node] = \left\{

  0node.left.val≠node.val∧node.right.val≠node.valdp[node.left]+1node.val=node.left.val∧node.val≠node.right.valdp[node.right]+1node.val=node.right.val∧node.val≠node.left.valmax(dp[node.left]+1,dp[node.right]+1)node.left.val=node.right.val=node.val" role="presentation" style="position: relative;">0dp[node.left]+1dp[node.right]+1max(dp[node.left]+1,dp[node.right]+1)node.left.val≠node.val∧node.right.val≠node.valnode.val=node.left.val∧node.val≠node.right.valnode.val=node.right.val∧node.val≠node.left.valnode.left.val=node.right.val=node.val$$\begin{array}{rlr}& 0& node.left.val\ne node.val\wedge node.right.val\ne node.val\\ & dp[node.left]+1& node.val=node.left.val\wedge node.val\ne node.right.val\\ & dp[node.right]+1& node.val=node.right.val\wedge node.val\ne node.left.val\\ & max(dp[node.left]+1,dp[node.right]+1)& node.left.val=node.right.val=node.val\end{array}$$
  \right. dp[node]=⎩ ⎨ ⎧​​0dp[node.left]+1dp[node.right]+1max(dp[node.left]+1,dp[node.right]+1)​node.left.val=node.val∧node.right.val=node.valnode.val=node.left.val∧node.val=node.right.valnode.val=node.right.val∧node.val=node.left.valnode.left.val=node.right.val=node.val​

• 结果值则为递归过程中最大的$dp[node.left]+node.right$

代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:
        ret = 0
        def dfs(node: Optional[TreeNode]) -> int:
            nonlocal ret
            if not node:
                return 0
            left = dfs(node.left)
            right = dfs(node.right)
            leftLength = left + 1 if node.left and node.val == node.left.val else 0
            rightLength = right + 1 if node.right and node.val == node.right.val else 0
            ret = max(ret, leftLength + rightLength)
            return max(leftLength, rightLength)
        dfs(root)
        return ret
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

复杂度

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$