Longest Univalue Path


@cheesewraps A path is between two nodes, so both trees have an expected answer of 2.

@cheesewraps
Count number of edges and not number of nodes. 2 is correct answer here.

Same idea.
class Solution { int max = 0; public int longestUnivaluePath(TreeNode root) { max = 0; if(root == null) return 0; return Math.max(longestUnivaluePathHelper(root.left,root.val) + longestUnivaluePathHelper(root.right,root.val),max); } public int longestUnivaluePathHelper(TreeNode root,int parent_val){ if(root == null) return 0; int left = longestUnivaluePathHelper(root.left,root.val); int right = longestUnivaluePathHelper(root.right,root.val); max = Math.max(max,left + right); return root.val == parent_val ? 1 + Math.max(left,right) : 0; } }

@awice
Could you explain why is answer 2 here ? There is only one path between 44( left) and 44(right)...max of both is 1
1
/
4 5
/ \
4 4 5

@12GitTho10
Question is asking for longest path which has same node value
combine both left and right
so the path is
leftmost 4 > middle 4 > right down 4as all node values is 4 we have to consider all
Hope this will help.


Postorder based on "max path in binary tree":
class Solution { public: int max_path = 0; int longestUnivaluePath(TreeNode* root) { postorder(root); return max_path; } int postorder(TreeNode* root) { if (root == nullptr) return 0; int left_length = postorder(root>left); int right_length = postorder(root>right); int lhs = sameas(root>left, root>val) ? left_length : 0; int rhs = sameas(root>right, root>val) ? right_length : 0; max_path = max(max_path, lhs + rhs); return max(lhs, rhs) + 1; } bool sameas(TreeNode* node, int value) { return node && node>val == value; } };

@wqmbisheng which is correct because there are two edges, root to left and root to right.

Definition for a binary tree node.
class TreeNode(object):
def init(self, x):
self.val = x
self.left = None
self.right = None
class Solution(object):
def longestUnivaluePath(self, root):
"""
:type root: TreeNode
:rtype: int
"""
res = [0]
def front_digui(root,res):
"""利用递归实现树的先序遍历"""
if root == None:
return 0
left= front_digui(root.left,res)
right= front_digui(root.right,res)
if root.left:
left=left+1 if (root.left.val == root.val ) else 0
if root.right:
right=right+1 if (root.right.val == root.val ) else 0
res[0] = max(res[0],left+right)
return max(left, right)
front_digui(root,res)
return res[0]

There appears to be a discrepancy between the task described and the results they desire for this question. Gives the problem description, their test tree of [1,4,5,4,4,null,5] should return 1, but their expected result returns 2 for this tree. Analyzing their expected solution on the test tree [5,5,5,5,1,5] suggested by another user below shows that their solution returns 4, when it should return 2, which makes me think their solution code is incorrectly including some sort of summation (that test tree includes two paths tied for longest length which are both of length 2).

@awice I think some test cases are wrong for this problem. An input like [5,5,5,5,5,4,5] shows Expected answer as 4. But according to the problem description the Correct answer should be 5. Please correct me if I understood the question wrong.

@piku We are counting the edges and not the nodes. The input
[5,5,5,5,5,4,5]
creates a tree like:5 / \ 5 5 / \ / \ 5 5 4 5
which has the following longest path with 4 edges:
5 / \ 5 5 / \ 5 5