Python Simple to Understand


  • 5

    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.

    Imgur

    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 = [0]
            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[0] = max(longest[0], left + right)
                return max(left, right)
            traverse(root)
            return longest[0]
    

  • 2
    C

    Great solution!

    I really liked how you defined left and 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.


  • 0
    P

    @yangshun said in Python Simple to Understand:

    Diameter of Binary Tree

    Is there a particular reason why you declare longest an array instead of a variable?


  • 2

    @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).


  • 0
    P

    @yangshun So would the following example be a use of Python's 3 nonlocal?

    https://discuss.leetcode.com/topic/83481/python-simple-with-explanation

    He does use a variable to modify it, hence my confusion with the use of an array.


  • 1
    A

    @proenca he used self.variable (class variable) in stead of a local variable.


  • 1
    V

    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
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.