Python 奇怪的返回问题

Question

我正在尝试实现一个函数，它接受两个根节点(二叉树)并遍历并检查它们是否相同。这是我到目前为止的进展；

def inorder(p, q):
  if p and q:
    inorder(p.left, q.left)
    if p.val != q.val:
      return False
    inorder(p.right, q.right)
    return True

即使当我在函数中添加一些打印时我可以看到 p.val 显然不等于 q.val 它仍然返回正确。我想不通。是否因为递归堆栈调用而返回两次？

Answer 1

您的代码没有检查子级 inorder 调用的结果。如果 p 和 q 具有相同的根值，您将始终返回 True，即使 inorder(p.left, q.left ) 返回了 False。这是更正后的代码:

def inorder(p, q):
    if p is None and q is None:
        return True
    elif p is not None and q is not None:
        return (
            p.val == q.val 
            and inorder(p.left, q.left)
            and inorder(p.right, q.right)
        )