为什么调用此方法时无显示？

Question

我想编写方法mirror()，该方法创建并返回二叉树，其中所有左子树都变为右子树，反之亦然。我试图通过递归来做到这一点：

def mirror(self):
    if self.left == None and self.right == None:
        return
    elif self.left == None and self.right != None:
        t = self.right
        self.right = self.left
        self.left = t
        self.left.mirror()
    elif self.left != None and self.right == None:
        t = self.right
        self.right = self.left
        self.left = t
        self.right.mirror()
    else:
        t = self.right
        self.right = self.left
        self.left = t
        self.left.mirror()
        self.right.mirror()

但是我得到输出None。为什么以及如何解决？

Answer 1

您当前的函数就地交换所有分支；无需特别返回树，因为如果您首先设法调用该方法，则已经有对其的引用。但是，如果您仍然想返回这样的引用，则可以：

def mirror(self):
    if self.left == None and self.right == None:
        pass
    elif self.left == None and self.right != None:
        t = self.right
        self.right = self.left
        self.left = t
        self.left.mirror()
    elif self.left != None and self.right == None:
        t = self.right
        self.right = self.left
        self.left = t
        self.right.mirror()
    else:
        t = self.right
        self.right = self.left
        self.left = t
        self.left.mirror()
        self.right.mirror()
    return self

或更简单地说：

def mirror(self):
    if self.left is not None:
        self.left.mirror()
    if self.right is not None:
        self.right.mirror()
    self.left, self.right = self.right, self.left
    return self

另一方面，如果想要独立于原始树的new树，则需要构造一个树以返回。

def mirror(self):
    new_tree = ...  # Whatever you do to create a root node from the root of self

    # If the child pointers aren't already None after creating the node
    new_tree.left = None
    new_tree.right = None

    if self.right is not None:
        new_tree.left = self.right.mirror()
    if self.left is not None:
        new_tree.right = self.left.mirror()

    return new_tree