LeetCode 问题 same Tree，当输入包含 "Null" 时，为什么我的代码会失败？

Question

我正在看 LeetCode 题 "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.

我的代码通过了一些测试用例，但未通过其他测试用例。

我的具体问题是测试用例 [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

您的代码假定两棵树的形状相同。但是，如果一棵树有 child 而另一棵树没有，则您的代码永远不会访问 child，并且当树的其余部分相同时，这将给出误报。仅存在这样的 child（在另一棵树中不存在）就足以指示中止该过程并且 return False.

至于算法本身。可惜你这样做了:

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

...当您实际上可以立即比较这两个值时（而不是在最后才这样做）。为什么不检查 p.val == q.val 如果那不是真的，请停止进一步查找？另一方面，如果它们相等，则也没有理由将这些值附加到列表中。它只是表示“到目前为止一切顺利”，您可以继续...

总结：

Return 两边都没有节点时为真(None)
Return 当一侧有一个节点而另一侧不存在时为假
Return对应节点的值不同时为false
Return 当且仅当递归也 returns 对于两个 children.

已实施：

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

让我们看看以下输入的“answer1”和“answer2”变量：

输入：

[1,2] [1,null,2]

输出：

answer1 = answer2 = [1]

如您所见，一旦您的 helperFunction 中的值“p”或“q”之一为空，您的程序就会错误地停止比较两棵树的节点。这是由于以下代码行：

if p != None and q != None:

您的错误的简单修复可能是这样的：

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)

LeetCode 问题 same Tree，当输入包含 "Null" 时，为什么我的代码会失败？

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

python

algorithm

binary-tree

data-structures