解决 LeetCode 挑战“合并两棵二叉树”时出现属性错误

Question

我正在尝试解决LeetCode问题617。合并两棵二叉树:

给你两个二叉树

root1

和

root2

。

想象一下，当您将其中一棵树覆盖另一棵树时，两棵树的某些节点重叠，而其他节点则不重叠。您需要将两棵树合并成一个新的二叉树。合并规则是，如果两个节点重叠，则将节点值相加作为合并节点的新值。否则，NOT null 节点将用作新树的节点。

返回合并后的树。

为了执行它，我创建了一棵新树并尝试将两个节点的值分配为新节点的值。但是，我无法为二叉树中的一个子节点分配值。

这是我的代码：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def mergeTrees(self, root1, root2):
        if not root1 and not root2:
            return

        if root1 and root2:
            root3 = TreeNode(root1.val + root2.val)
            print(root3)
        elif root1:
            root3 = TreeNode(root1.val)
        elif root2:
            root3 = TreeNode(root2.val)

        root3.left = self.mergeTrees(root1.left, root2.left)
        root3.right = self.mergeTrees(root1.right, root2.right)

        return root3

# My driver code: create two trees and call above method
p = TreeNode(1)
p.left = TreeNode(2)
p.left.left = TreeNode(3)
p.left.right = TreeNode(4)
p.right = TreeNode(2)
p.right.left = TreeNode(4)
p.right.right = TreeNode(3)

q = TreeNode(1)
q.left = TreeNode(2)
q.left.left = TreeNode(4)
q.left.right = TreeNode(5)
q.left.left.left = TreeNode(8)
q.left.left.right = TreeNode(9)
q.right = TreeNode(3)
q.right.left = TreeNode(6)
q.right.right = TreeNode(7)

merged = Solution().mergeTrees(p, q)

我得到的结果：

AttributeError：“NoneType”对象没有属性“left”

我的错误是什么？

Answer 1

当您进行递归调用并作为参数传递

root1.left

，但不验证

root1

是否为

None

时，会发生错误。如果

root1

是

None

，您会收到该错误，该错误正确地表明它没有属性

left

。

修正很简单：如果

root1

是

None

，只需传递

None

作为参数而不是

root1.left

。对于第二个参数和第二个递归调用也应该执行相同的操作。

更正：

    root3.left = self.mergeTrees(root1 and root1.left, root2 and root2.left)
    root3.right = self.mergeTrees(root1 and root1.right, root2 and root2.right)

这里我们评估表达式

root1 and root1.left

。如果

root1

是

None

，它是一个假值，因此表达式的计算结果为

root1

，即

None

。如果

root1

不是

None

，则表达式计算为

and

运算的第二个操作数，即

root1.left

。

备注

不相关，但您可以通过不创建新节点来获得一些执行时间，特别是当遇到两棵树中只有一棵在给定位置仍有节点的情况时。在这种情况下，您可以停止递归并仅返回该节点 - 以及它下面可能具有的子树。