Python Simple to Understand


  • 9

    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.

    - Yangshun

    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.


  • 2
    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
    

  • 0
    C

    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
    

    Returns 2


  • 1
    V

    @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
    

  • 0
    C

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

    Thank you!


  • 0
    S

    good! humm..maybe use self.longest instead of [0]


Log in to reply
 

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