How to get over this specific testcase while traversing tree in inorder traversal?

I'm trying to solve 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.

I've approached this using DFS, and implementing preorder and postorder traversal. These all passed all the test cases.

The problem is when I tried using inorder traversal, it got wrong on the 58th test case out of 60. And I can't fix it. Could you please help me to get out of this test case using inorder traversal?

I am adding the code along with the test case's picture here. Thank you.

# 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 isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        def inorder(root,q):
            if root:
                inorder(root.left,q)
                q.append(root.val)
                inorder(root.right,q)
            else:
                q.append(None)
            
            return q

        q1 = inorder(p,[])
        q2 = inorder(q,[])
        print(q1)
        print(q2)

        return q1==q2

Your code is collecting the tree's values in inorder sequence, including the None values for when there is no corresponding child node. It compares these inorder sequences made from the two trees. But this idea for an algorithm overlooks the fact that two differently shaped trees can have the same inorder sequence. In other words, an inorder sequence does not uniquely identify a binary tree.

Taking the example input:

      1
     / \
    1   None
   / \
None  None

...we get [None,1,None,1,None] as sequence, but the following tree results in the same list:

      1
     / \
 None   1
       / \
    None  None

So you'll have to adapt the output from the inorder sequence in such a way that it is unique for each tree shape. There are several ways you can do that. One is to make your q list nested:

       def inorder(root):
            if root:
                q = [inorder(root.left),
                     root.val,
                     inorder(root.right)]
            else:
                q = None
            
            return q

        q1 = inorder(p)
        q2 = inorder(q)
        print(q1)
        print(q2)

        return q1==q2

Note that there is a solution that does not require to create a list, so the problem can be solved without O(n) auxiliary memory.

Hint:

Traverse both trees in "parallel"

... and a corresponding solution spoiler:

return p == q or ( p and q and p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right) )