Wrong Answer? Beg to differ.


  • 0
    Q

    Here's my solution in Python for Binary Tree Level Order Traversal:

    class Solution:
    	traversal = []
    	depth = -1
    
    	# @param root, a tree node
    	# @return a list of lists of integers
    	def levelOrder(self, root):
    		if root == None:
    			return Solution.traversal
    
    		Solution.depth += 1
    		if Solution.depth == len(Solution.traversal):
    			Solution.traversal.append([root.val])
    		else:
    			(Solution.traversal[Solution.depth]).append(root.val)
    
    		self.levelOrder(root.left)
    		self.levelOrder(root.right)
    
    		Solution.depth -= 1
    		return Solution.traversal
    

    For the test case {1, 2}, OJ will produce output [[1, 1], [2]], but my own machine gives the correct answer [[1], [2]]. Did I understand something wrong here or is there a bug in OJ?


  • 1
    M

    Global and static variables persist between runs, so traversal will need to be reset between runs, or you'll get wrong answers in future inputs. Since you don't reset it, the answer to the previous input is still stored in traversal, and is included in your solution.

    Based on the output, the previous, and first, input, was {1}. It was stored in traversal as [1], and in the second input, depth (0) was not equal to the length, so it appended the list, giving you [[1,1]], before moving onto the child, resulting in [[1,1],[2]], the output provided.

    Please see "Why does my code produce a different output compared to my local environment?", part 1.


Log in to reply
 

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