题目描述
给定一个二叉树,找到最长的路径,这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
注意:两个节点之间的路径长度由它们之间的边数表示。
示例
输入: 5 / \ 4 5 / \ \ 1 1 5 输出: 2
思路
1.可以根据题意推导出本题的公式:rootPathVal = Math.max(leftPathVal,rightPathVal)。
2.可以看出此题可以使用递归思想求解。
3.若leftVal == rootVal,则leftPathVal = leftPathVal + 1,否则leftVal = 0 ,因为只有相同时,leftVal才可以作为同路径的参考;rightVal也是同理。
Java代码实现
class Solution { private int res = 0; public int longestUnivaluePath(TreeNode root) { if(root == null){ return 0; } longestUnivaluePathBFS(root); return res; } public int longestUnivaluePathBFS(TreeNode root) { if(root == null){ return 0; } int left = longestUnivaluePathBFS(root.left); int right = longestUnivaluePathBFS(root.right); if(root.left != null && root.left.val == root.val){ left = left + 1; }else{ left = 0; } if(root.right != null && root.right.val == root.val){ right = right + 1; }else{ right = 0; } res = Math.max(res,left+right); return Math.max(left,right); } }
Golang代码实现
var maxVal int = 0 func longestUnivaluePath(root *TreeNode) int { longestUnivaluePathBFS(root) return maxVal } func longestUnivaluePathBFS(root *TreeNode) int { if root == nil{ return 0 } left := longestUnivaluePathBFS(root.Left) right := longestUnivaluePathBFS(root.Right) if root.Left != nil && root.Left.Val == root.Val{ left = left + 1 }else { left = 0 } if root.Right != nil && root.Right.Val == root.Val{ right = right + 1 }else { right = 0 } if left+right>maxVal{ maxVal = left+right } if left>right { return left }else { return right } }