0687. Longest Univalue Path

题目信息

题号:

0687

难度:

Medium

主题:

二叉树、同值路径、任意起终点、边数

原题:

LeetCode 0687

重点:

路径上所有节点值必须相同、相邻节点由父子边连接、路径不要求经过根、长度按边数而不是节点数计算

题目重述

给定二叉树根节点 root,寻找一条路径,使路径上的所有节点具有相同的值,并返回该路径包含的边数最大值。

路径可以从任意节点开始、在任意节点结束,但相邻节点必须通过树中的父子边连接,且不能重复经过节点;路径不一定经过根节点。空树或只有一个节点的路径长度为 0。树中节点数位于 [0, 10^4],节点值位于 [-1000, 1000]。

自建示例

最长路径位于一个子树中:

输入:root = [2,2,3,2,2,3,3]
输出:2
解释:左子树中两个值为 2 的叶节点可通过它们的父节点连接,路径包含两条边;右侧值为 3 的子树也能形成长度 2 的路径。

同值节点形成单链:

输入:root = [7,7,null,7]
输出:2
解释:三个值为 7 的节点沿父子关系连接,最长路径包含两条边。