LeetCode Problem same Tree, why does my code fail when input contains "Null"?-CodePudding

I am looking at the LeetCode problem "100. Same Tree":

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

My code passes some test cases and fails others.

My specific problem is with the test case [1,2] and [1,null,2]. Python uses None not null. When I use my local code editor (visual studio code) it produces the expected output. I know I could implement this in other ways but I don't understand why this solution won't work on LeetCode.

Here is my code:

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        answer1 = []
        answer2 = []
        self.helperFunction(p, q, answer1, answer2)
        
        for i in range(len(answer1)):
            if answer1[i] != answer2[i]:
                return False   
        return True
    
    
    def helperFunction(self, p, q, answer1, answer2):
        if p != None and q != None:
            self.helperFunction(p.left, q.left, answer1, answer2)
            answer1.append(p.val)
            answer2.append(q.val)
            self.helperFunction(p.right, q.right, answer1, answer2)

CodePudding user response：

Your code assumes that both trees have the same shape. If however one tree has a child where the other doesn't, your code never visits that child, and this will give false positives when the rest of the tree is the same. The mere presence of such a child (that does not exist in the other tree) would be enough indication to abort the process and return False.

As to the algorithm itself. It is a pity that you do this:

    answer1.append(p.val)
    answer2.append(q.val)

...when you could actually compare these two values immediately (instead of doing this at the very end). Why not check p.val == q.val and if that is not true, stop looking any further? On the other hand, if they are equal, there is no reason to append those values to lists either. It just means "so far so good", and you can continue...

Concluding:

Return True when at both sides there is no node (None)
Return False when on one side you have a node that is not there on the other side
Return False when the values of corresponding nodes are different
Return True if and only when the recursion also returns True for both children.

Implemented:

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        return bool(not p and not q     or
                    p and q and p.val == q.val and self.isSameTree(p.left, q.left) 
                                               and self.isSameTree(p.right, q.right))

CodePudding user response：

The helperFunction does nothing if only one node is None/null, which causes the inorder traversal logic to fail. To handle those cases, you can just append the non-null node's value.

def helperFunction(self, p, q, answer1, answer2):
    if p and q:
        self.helperFunction(p.left, q.left, answer1, answer2)
        answer1.append(p.val)
        answer2.append(q.val)
        self.helperFunction(p.right, q.right, answer1, answer2)
    elif p:
        answer1.append(p.val)
    elif q:
        answer2.append(q.val)

Additionally, when you are comparing the lists, you need to handle the case where list sizes can be different.

def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
    answer1 = []
    answer2 = []
    self.helperFunction(p, q, answer1, answer2)
    if len(answer1) != len(answer2):
        return False
    
    for i in range(len(answer1)):
        if answer1[i] != answer2[i]:
            return False   
    return True