The approach is similar to the Diameter of Binary Tree question except that we reset the left/right to 0 whenever the current node does not match the children node value.
In the Diameter of Binary Tree question, the path can either go through the root or it doesn't.
Hence at the end of each recursive loop, return the longest length using that node as the root so that the node's parent can potentially use it in its longest path computation.
We also use an external variable
longest that keeps track of the longest path seen so far.
class Solution(object): def longestUnivaluePath(self, root): """ :type root: TreeNode :rtype: int """ # Time: O(n) # Space: O(n) longest =  def traverse(node): if not node: return 0 left_len, right_len = traverse(node.left), traverse(node.right) left = (left_len + 1) if node.left and node.left.val == node.val else 0 right = (right_len + 1) if node.right and node.right.val == node.val else 0 longest = max(longest, left + right) return max(left, right) traverse(root) return longest
I really liked how you defined
right so elegantly, making it clear that the path containing the left branch is either extended when
node.left.val == node.val or reset to 0 (and same for the right). I had not thought of this binary situation so clearly.
Diameter of Binary Tree
Is there a particular reason why you declare longest an array instead of a variable?
@proenca In Python 2 you cannot modify variable references outside of the function. In Python 3 there's
nonlocal but that does not exist in Python 2. Hence this is a common hack where we use an array containing a single value and modify that value instead (the reference to the array is preserved).
@yangshun So would the following example be a use of Python's 3 nonlocal?
He does use a variable to modify it, hence my confusion with the use of an array.
@proenca he used self.variable (class variable) in stead of a local variable.
Nice solution! I think the code can be simplified further if we include an additional parameter for the parent node's value to the
traverse function, as below.
class Solution(object): def longestUnivaluePath(self, root): """ :type root: TreeNode :rtype: int """ self.longest = 0 def traverse(node, parent_val): if not node: return 0 left, right = dfs(node.left, node.val), dfs(node.right, node.val) self.longest = max(self.longest, left + right) return 1 + max(left, right) if node.val == parent_val else 0 traverse(root, None) return self.longest
why doesn't traverse ever return left + right? I feel like the following tree
4 / \ 4 5 / \ \ 4 4 5
should return 3 since the following tree
1 / \ 4 5 / \ \ 4 4 5
@cheesewraps The result for the first tree should be 2 because the following paths are each 2 segments long.
4 4 / / 4 4 4 / \ / \ 4 4 4 4
@vliao thank you for affirming that the solution is correct. I've been having a tough time wrapping my head around it. I was sort of thinking that why can the path "go up and over" in one situation but not in another. But I think I am missing the point. The point being that you can't follow multiple paths.
In my assertion that the one example should have three, I am wrong in my thinking because there is a place where I have chosen to follow in two different paths.
I'm not sure that made sense, but maybe it did.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.