使用链表遍历二叉树

Question

>我正在尝试使用链表对二叉树进行预序遍历。

class BTNode:
"""A node in a binary tree."""
    def __init__(self: 'BTNode', item: object, 
             left: 'BTNode' =None, right: 'BTNode' =None) -> None:
        self.item, self.left, self.right = item, left, right

class LLNode:
    """A node in a linked list."""
    def __init__(self: 'LLNode', item: object, link: 'LLNode' =None) -> None:
        self.item, self.link = item, link
    def __str__(self: 'LLNode') -> str:
        """Return an informative string showing self
        >>> b = LLNode(1, LLNode(2, LLNode(3)))
        >>> str(b)
        '1 -> 2 -> 3'
        """
        return str(self.item) + (' -> ' + str(self.link) if self.link else '')


def preorder(root: BTNode) -> LLNode:
    """Return the first node in a linked list that contains every value from the
    binary tree rooted at root, listed according to an preorder traversal.
    >>> b = BTNode(1, BTNode(2), BTNode(3))
    >>> repr(preorder(b))
   'LLNode(1, LLNode(2, LLNode(3)))'
   >>> b2 = BTNode(4, BTNode(5))
   >>> b3 = BTNode(7, b, b2)
   >>> str(preorder(b3))
   '7 -> 1 -> 2 -> 3 -> 4 -> 5'
    """
    return _preorder(root)[0]
def _preorder(root: BTNode) -> (LLNode, LLNode):
    """Return the first and last nodes in a linked list that contains every
    value from the binary tree rooted at root, listed according to an preorder
    traversal.
    """
    if not root:
        return None, None
    left_head, left_tail = _preorder(root.left)
    right_head, right_tail = _preorder(root.right)
    # change from right_tail = left_tail to right_tail = left_head
    if not right_tail:
        right_tail = left_head
    if not left_head:
        left_head = right_head
    if left_tail:
        left_tail.link = right_head
    root_node = LLNode(root.item, left_head)
    return root_node, right_tail

我总是得到"7 -> 1 -> 2"而不是"7 -> 1 -> 2 -> 3 -> 4 -> 5"作为我在预购函数中的输出。我不太确定为什么。有人可以告诉我如何编辑当前代码来解决此问题吗？

Answer 1

您的预购代码中似乎有一个错误，处理像 LLNode(value, None) 这样的退货。

具体来说，当您遍历b和c都没有子项的BTNode(a, BTNode(b), BTNode(c))时，您不会正确合并。您需要再次查看此案例的逻辑。

Answer 2

您没有正确返回列表的尾部。 我添加了一些调试检测来跟踪_preorder的操作 - 这是您在此处发布之前应该做的事情。 调试是一项关键技能。

indent = ""
def _preorder(root: BTNode) -> (LLNode, LLNode):
    """Return the first and last nodes in a linked list that contains every
    value from the binary tree rooted at root, listed according to an preorder
    traversal.
    """
    global indent
    print(indent, "  ENTER", root.item if root else "NULL")
    if not root:
        return None, None
    indent += "  "
    left_head, left_tail = _preorder(root.left)
    print (indent, root.item, "Left ", left_head, left_tail, str(left_head))
    right_head, right_tail = _preorder(root.right)
    print (indent, root.item, "Right", right_head, right_tail, str(right_head))
    if not right_tail:
        right_tail = left_tail
    if not left_head:
        left_head = right_head
    if left_tail:
        left_tail.link = right_head
    root_node = LLNode(root.item, left_head)
    print (indent, "LEAVE", root.item, right_tail.item if right_tail else "NULL")
    indent = indent[2:]
    return root_node, right_tail

完整遍历的输出如下。 您可以看到您从未正确链接右侧;我会把维修留给学生作为练习。 :-)

   ENTER 7
     ENTER 1
       ENTER 2
         ENTER NULL
       2 Left  None None None
         ENTER NULL
       2 Right None None None
       LEAVE 2 NULL
     1 Left  2 None 2
       ENTER 3
         ENTER NULL
       3 Left  None None None
         ENTER NULL
       3 Right None None None
       LEAVE 3 NULL
     1 Right 3 None 3
     LEAVE 1 NULL
   7 Left  1 -> 2 None 1 -> 2
     ENTER 4
       ENTER 5
         ENTER NULL
       5 Left  None None None
         ENTER NULL
       5 Right None None None
       LEAVE 5 NULL
     4 Left  5 None 5
       ENTER NULL
     4 Right None None None
     LEAVE 4 NULL
   7 Right 4 -> 5 None 4 -> 5
   LEAVE 7 NULL
Main: 7 -> 1 -> 2

---

对 OP 更新的响应

显然，这解决了您问题的部分。 现在，让我们看看当您从节点 1 的左右子树的调用中返回时会发生什么，并尝试将它们正确链接到线性列表中：

left_head, left_tail = _preorder(root.left)
# returns 2, None
right_head, right_tail = _preorder(root.right)
# returns 3, None
if not right_tail:
    right_tail = left_head
# right_tail is now node 2; this isn't correct: node 3 should be in that spot.
if not left_head:
# left_head is node 2; not an issue now
if left_tail:
# left_tail is None; not an issue now
return root_node, right_tail
# You return nodes 1 and 2;
#   you never linked node 2 to node 3.
# You need to fix this.