python 二叉树迭代器 - 为什么返回的节点变为无？

Question

我挠头一个小时了。

我使用迭代器和堆栈实现了二叉树的中序遍历。

class Node:
    def __init__(self, val, left, right):
        self.val = val
        self.left = left
        self.right = right


class BTIterator:
    def __init__(self, root):
        self.stack = []  # Use a list as a stack by using pop() & append()
        self.root = root
        self.leftmost = None

    def Run(self):
        node = self.root
        while (node.left != None):
            self.stack.append(node)
            node = node.left
        print(self.stack)
        self.leftmost = node
        print(self.leftmost.val)
        while (self.Next(node) != None):
            node = self.Next(node)
            print(node.val)

    def Next(self, node):
        if (node.left != None):
            while (node.left != None):
                self.stack.append(node.left)
                node = node.left
            return node

        elif (node.right != None):
            node = node.right
            while (node.left != None):
                self.stack.append(node)
                node = node.left
            return node

        else:
            if self.stack != []:
                node = self.stack.pop()
                node.left = None
                return node

if __name__ == '__main__':
    # Let's construct the tree.
    n12 = Node(12, None, None)
    n11 = Node(11, None, n12)
    n9 = Node(9, None, None)
    n10 = Node(10, n9, n11)
    n15 = Node(15, None, None)
    n13 = Node(13, n10, n15)
    n5 = Node(5, None, None)
    n3 = Node(3, None, n5)
    n7 = Node(7, n3, n13)

    bti = BTIterator(n7)
    bti.Run()

我还在 IDE 上运行了上面的实现。从调试中，我清楚地看到 def Next(self, node) 返回 n7。但是，一旦 node = self.Next(node) 行获得 n7，它会将 n7 变为 None。为什么？!

我想这一定是我不知道的python语法。任何指针将不胜感激。

Answer 1

在你的实现中，我想指出三个问题:

1. 主要问题是您在 Next 中的实现不正确。因为中序遍历是left->root->right，if (node.left != None):部分是正确的，但是这里:

        elif (node.right != None):
            node = node.right
            while (node.left != None):
                self.stack.append(node)
                node = node.left
            return node

在处理 right child 之前，你应该先返回节点本身。

        else:
            if self.stack != []:
                node = self.stack.pop()
                node.left = None
                return node

而且您不仅应该在节点为叶节点时弹出，还应该将每个节点压入堆栈，并弹出每个Next。

1. 您不能将 Next 同时放在 while 条件和 block 中，因为它会调用两次。

while (self.Next(node) != None):
   node = self.Next(node)

1. != None in if (node.left != None): 在 python 中不需要，你可以只使用 if node.left:

因为Next有很多问题，所以我不得不重写Next，这里是我根据你的代码编辑的版本，我已经详细注释了:

class BTIterator:
    def __init__(self, root):
        self.stack = []  # Use a list as a stack by using pop() & append()
        self.root = root

    def Run(self):
        # find the left most node, which means then first node
        node = self.root
        while node.left:
            self.stack.append(node)
            node = node.left

        # start from left most node
        while node:
            print(node.val)
            node = self.Next(node)

    def Next(self, node):
        # find right node, if it is none, it's ok, we will deal with it afterwards
        node = node.right

        # reach the end
        if not self.stack and not node:
            return None

        # push left child iteratively
        while node:
            self.stack.append(node)
            node = node.left

        # this is next node we want
        return self.stack.pop()

希望对您有所帮助，如果您还有其他问题，请发表评论。 :)