专栏首页编程理解Leetcode 687. 最长同值路径

Leetcode 687. 最长同值路径

题目描述

给定一个二叉树,找到最长的路径,这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。

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

递归

最长路径值是由一个节点的左连续边长度,加上右连续边长度之和。不妨以 path(node) 函数表示 node 节点为端点的最长连续节点个数,则遍历二叉树,找到左、右连续节点个数和的最大值即可。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def longestUnivaluePath(self, root: TreeNode) -> int:
        self.ret=0
        def path(node):
            if not node:
                return 0
            l=path(node.left)
            r=path(node.right)
            l=l if node.left and node.left.val==node.val else 0
            r=r if node.right and node.right.val==node.val else 0            
            self.ret=max(l+r,self.ret)
            return max(l,r)+1
        path(root)
        return self.ret

代码中以 self.ret 表示路径长度,边数相对于点数减一,所以 self.ret=l+r。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构(八):邻接表与邻接矩阵

    邻接表和邻接矩阵是图的两种常用存储表示方式,用于记录图中任意两个顶点之间的连通关系,包括权值。

    zhipingChen
  • Leetcode 993. 二叉树的堂兄弟节点

    在二叉树中,根节点位于深度 0 处,每个深度为 k 的节点的子节点位于深度 k+1 处。

    zhipingChen
  • Leetcode 938. 二叉搜索树的范围和

    输入:root = [10,5,15,3,7,null,18], L = 7, R = 15

    zhipingChen
  • 算法导论第十三章 红黑树

      写在前面:这一章真的把我害惨了,之前至少尝试看过3遍,每次看之前都下定决定一定要把它拿下,可是由于内容较多,深度够深,以致于每次要不是中途有什么事放弃了就跳...

    CloudDeveloper
  • Jest进阶:接入ts、集成测试与覆盖率统计

    在给 vemojs 做完各种测试之后,导师很快提出了新的要求,给 clousebase-cli 编写测试用例。有个问题摆在眼前:它是用 typescript ...

    心谭博客
  • 复盘node项目中遇到的13+常见问题和解决方案

    笔者之前陆陆续续接手过几个nodejs项目, 也参与过几个有点意思的nodejs开源项目, 最近把其中遇到的一些问题和解决方案做一个梳理, 避免大家继续踩坑. ...

    徐小夕
  • (七)python3 只需3小时带你轻松入门——List与dict

    List列表 python中最基本的数据结构之一。序列(或者说集合)中的每个元素都分配一个数字用来表示它的位置(索引),第一个索引是0,第二个索引是1,依此类...

    公众号 碧油鸡
  • 10条很棒的Python一行代码

    自从我用Python编写第一行代码以来,我就被它的简单性、出色的可读性和特别流行的一行代码所吸引。在下面,我想介绍并解释其中一些一行程序—可能有一些您还不知道,...

    HuangWeiAI
  • python迭代器-迭代器取值-for循环-生成器-yield-生成器表达式-常用内置方法-面向过程编程-05

    迭代: # 更新换代(其实也是重复)的过程,每一次的迭代都必须基于上一次的结果(上一次与这一次之间必须是有关系的)

    suwanbin
  • LeetCode208. 实现 Trie (前缀树)

    mathor

扫码关注云+社区

领取腾讯云代金券