Leetcode 1372: Why do these two code snippets give different results?

Question

I am solving LeetCode problem 1372. Longest ZigZag Path in a Binary Tree:

You are given the root of a binary tree.

A ZigZag path for a binary tree is defined as follow:

Choose any node in the binary tree and a direction (right or left).

If the current direction is right, move to the right child of the current node; otherwise, move to the left child.

Change the direction from right to left or from left to right.

Repeat the second and third steps until you can't move in the tree.

Zigzag length is defined as the number of nodes visited - 1. (A single node has a length of 0).

Return the longest ZigZag path contained in that tree.

The following is an accepted solution:

# Definition for a binary tree node.

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.longest_path = 0

    def longestZigZag(self, root: Optional[TreeNode]) -> int:
        val1 = 1 + self.helper(root.right, 'r')
        val2 = 1 + self.helper(root.left, 'l')
        # print(val2, self.longest_path)
        val = max(val1, val2)
        return max(val, self.longest_path) - 1

    def helper(self, root, d):
        if root == None:
            return 0
        if d == 'l':
            l_path = 1 + self.helper(root.left, d='l')
            self.longest_path = max(self.longest_path, l_path)
            return 1 + self.helper(root.right, d='r')
        if d == 'r':
            r_path = 1 + self.helper(root.right, d='r')
            self.longest_path = max(self.longest_path, r_path)
            return 1 + self.helper(root.left, d='l')

Then I wanted to reduce the code a bit and pass the expression assigned to l_path directly as argument to max:

class Solution:
    def __init__(self):
        self.longest_path = 0

    def longestZigZag(self, root: Optional[TreeNode]) -> int:
        val1 = 1 + self.helper(root.right, 'r')
        val2 = 1 + self.helper(root.left, 'l')
        # print(val2, self.longest_path)
        val = max(val1, val2)
        return max(val, self.longest_path) - 1

    def helper(self, root, d):
        if root == None:
            return 0
        if d == 'l':
            self.longest_path = max(self.longest_path, 1 + self.helper(root.left, d='l'))
            return 1 + self.helper(root.right, d='r')
        if d == 'r':
            r_path = 1 + self.helper(root.right, d='r')
            self.longest_path = max(self.longest_path, r_path)
            return 1 + self.helper(root.left, d='l')

The only change is this line:

self.longest_path = max(self.longest_path, 1 + self.helper(root.left, d='l'))

My question:

The altered version returns different results. Why is that?

For instance, for this input the second version returns 1 (wrong) while the first version returns 2 (correct):

Encoded format for this input on HackerRank: [1,1,null,1,null,1,null,null,1]

Please make the problem reproducible by providing the minimal input for which the problem occurs. — trincot
– trincot, Commented Dec 21, 2024 at 9:26

trincot · Accepted Answer · 2024-12-21 09:55:10Z

4

The reason for the difference is the order of execution of the following two expressions:

1 + self.helper(root.left, d='l')
self.longest_path

helper can assign a new value to self.longest_path, so it matters whether you read self.longest_path before or after the call of self.helper -- the order of evaluation is important.

When avoiding the assignment to l_path, you can still get the correct order of execution by swapping the arguments passed to max.

This will give the correct result:

self.longest_path = max(1 + self.helper(root.left, d='l'), self.longest_path)
#                       ---------------------------- swapped ---------------

edited Dec 21, 2024 at 9:55

answered Dec 21, 2024 at 9:32

trincot

357k38 gold badges282 silver badges338 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

awz · Accepted Answer · 2024-12-21 05:04:49Z

-1

The second code is missing l_path = 1 + self.helper(root.left, d='l').

You can also simplify the code:

class Solution:
    def longestZigZag(self, root):
        def dfs(node):
            if not node:
                return [-1, -1, -1]
            l = dfs(node.left)
            r = dfs(node.right)
            return [l[1] + 1, r[0] + 1, max(l[1] + 1, r[0] + 1, l[2], r[2])]

        return dfs(root)[-1]

answered Dec 21, 2024 at 5:04

awz

1

Collectives™ on Stack Overflow

Leetcode 1372: Why do these two code snippets give different results?

My question:

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

My question:

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related