Given the root of a binary tree, return the length of the longest path, where each node in the path has the same value. This path may or may not pass through the root.
The length of the path between two nodes is represented by the number of edges between them.
Given the root of a binary tree, return the length of the longest path, where each node in the path has the same value. This path may or may not pass through the root.
The length of the path between two nodes is represented by the number of edges between them.
Example 1:
Input: root = [5,4,5,1,1,null,5]
Output: 2
Explanation: The shown image shows that the longest path of the same value (i.e. 5).
Example 2:
Input: root = [1,4,5,4,4,null,5]
Output: 2
Explanation: The shown image shows that the longest path of the same value (i.e. 4).
Constraints:
The number of nodes in the tree is in the range [0, 104].
-1000 <= Node.val <= 1000
The depth of the tree will not exceed 1000.
题意：给定一颗树，返回最长路径
最长路径定义：相同的值连接成为最长路径。
比如针对数组[1,1,null,1,null]
1-1-1 的路径是2
思路一：dfs
对于一颗树而言，最长路径包含几种情况
1. 左结点的最长路径
2. 右结点的最长路径
3. 使用根节点和左右节点构成的最长路径
longest = max(1,2,3)
所以dfs函数需要往上抛使用了当前节点一边的最长路径，注意只能使用left的一边或者right的一边。
而计算当前节点的最长路劲则需要考虑两边都用上。
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func longestUnivaluePath(root *TreeNode) int {
var (
longest = 0
)
dfs(root, &longest)
return longest
}
func dfs(node *TreeNode, longest *int) int {
if node == nil {
return 0
}
leftRes, rightRes := 0, 0
curMaxRes,curRes := 0, 0
if node.Left != nil {
leftRes = dfs(node.Left, longest)
}
if node.Right != nil {
rightRes = dfs(node.Right, longest)
}
if node.Left != nil && node.Left.Val == node.Val {
curMaxRes += leftRes + 1
curRes += leftRes + 1
}
if node.Right != nil && node.Right.Val == node.Val {
curMaxRes += rightRes + 1
if rightRes+1 > curRes {
curRes = rightRes + 1
}
}
if curMaxRes > *longest {
*longest = curMaxRes
}
return curRes
}