LeetCode 问题同一个树，为什么我的代码在输入包含 "Null" 时失败？

Question

我正在看LeetCode问题"100。同样的Tree":

给定两棵二叉树p和q的根，写一个函数检查它们是否相同

如果两个二叉树结构相同，且节点值相同，则认为它们是相同的。

我的代码通过了一些测试用例，而另一些则失败了。

我的具体问题是测试用例[1,2] and [1,null,2]。Python使用None而不是null。当我使用本地代码编辑器(visual studio代码)时，它会产生预期的输出。我知道我可以用其他方式实现这个，但我不明白为什么这个解决方案在LeetCode上不起作用。

下面是我的代码:

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)

Answer 1

您的代码假设两棵树具有相同的形状。然而，如果一棵树有一个子树而另一棵树没有，那么你的代码永远不会访问该子树，当树的其余部分相同时，这将给出假阳性。仅仅存在这样的子节点(在另一个树中不存在)就足以提示中止进程并返回False。

关于算法本身。很遗憾你这样做:

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

…当您可以立即比较这两个值时(而不是在最后才这样做)。为什么不检查p.val == q.val，如果那不是真的，停止进一步研究?另一方面，如果它们相等，也没有理由将这些值附加到列表中。它的意思是"到目前为止一切顺利"，你可以继续…

结束:

• 当两边都没有节点时返回True (None)
• 当一边有一个节点而另一边不存在时返回False
• 当对应节点的值不同时返回False
• 当且仅当递归对两个子级都返回True时返回True。

实现:

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))

Answer 2

让我们看看你的"答案"。和";answer2"以下输入的变量:

输入:

[1, 2](1, null, 2)

输出:

answer1 = answer2 = [1]

正如你所看到的，你的程序错误地停止比较两棵树的节点，一旦其中一个值"p"或";q"在你的helperFunction中为null。这是由于下面的代码行:

if p != None and q != None:

一个简单的修复你的bug的方法是:

def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
answer1 = []
answer2 = []
self.helperFunction(p, q, answer1, answer2) # changed

return answer1 == answer2

def helperFunction(self, p, q, answer1, answer2):
if p != None and q != None:
self.helperFunction(p.left, q.left, answer1, answer2)
self.helperFunction(p.right, q.right, answer1, answer2)
if p is None:
answer1.append(None)
else:
answer1.append(p.val)

if q is None:
answer2.append(None)
else:
answer2.append(q.val)