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.
By Yang Shun
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
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.