Same tree verification through recursive tree traversal-CodePudding

I've prepared a recursive tree-traversal based solution to the "same tree" problem. However, I'm encountering an error on use cases involving None values. Why is my approach incorrect and how should I be altered to handle the use case?

class Solution(object):
    
    def traversal(self,root):
        visited = []
        
        if root:
            if root.left:
                visited.extend(self.traversal(root.left))

            visited.append(root.val)

            if root.right:
                visited.extend(self.traversal(root.right))   
            
        return visited             
    
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
    
        p_path = self.traversal(p)
        q_path = self.traversal(q)
        print(p_path, q_path)
        return p_path == q_path

Use case: input([1,1][1,null,1]), output(true), stdout([1,1], [1,1])

CodePudding user response：

Two different trees can have the same in-order traversal, but different structure, so it's not sufficient to completely rely on "traversal" in your code.

Hint: trees are only the same if they have the same root and (recursively) the same left subtree and (recursively) the same right subtree.

CodePudding user response：

Gave up on the recursive attempt, but an iterative one worked.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):             
    
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        stack = [(p,q)]
        while stack:
            p_curr, q_curr = stack.pop()
            
            # both p and q exist
            if p_curr and q_curr:
                
                # validity check
                if p_curr.val != q_curr.val:
                    return False
                
                # left check
                if p_curr.left and q_curr.left:
                    stack.append((p_curr.left, q_curr.left))
                elif p_curr.left and not q_curr.left:
                    return False
                elif not p_curr.left and q_curr.left:
                    return False
                
                # right check
                if p_curr.right and q_curr.right:
                    stack.append((p_curr.right, q_curr.right))
                elif p_curr.right and not q_curr.right:
                    return False
                elif not p_curr.right and q_curr.right:
                    return False                
                    
            
            elif p_curr:
                # only p exists, invalid
                return False
            
            elif q_curr:
                # only q exists, invalid
                return False
        
        return True