中序遍历树时如何克服这个特定的测试用例？

Question

问题链接

如果给定两棵树是否相同，则问题需要返回。所以我已经使用 dfs 解决了这个问题，并实现了前序和后序遍历。这些都通过了所有的测试用例。 问题是当我尝试使用中序遍历时，它在 60 个测试用例中的第 58 个测试用例上出错了。 我无法修复它。你能帮我用中序遍历摆脱这个测试用例吗？

我在这里添加代码和测试用例的图片。谢谢。

# 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

Answer 1

您的代码按顺序收集树的值。它比较由两棵树生成的有序序列。但是这个算法的想法忽略了一个事实，即两个不同形状的树可以具有 same 顺序序列。换句话说，一个中序序列并不能唯一标识一棵二叉树。

例如，这两棵树的顺序相同：

     3                    2
    / \                  / \
   2   4                1   4
  /                        /
 1                        3

所以你必须放弃这个想法并寻找不同的算法。