发表于 2024.04.13

• 二叉树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 题目链接