转换二进制搜索树到排序双链表

Question

在我的解决方案中，我遇到了一个“None's not have.val”的问题。。。我想知道如何调试它。。。

以下是描述

将BST转换为已排序的循环双链接列表。将左指针和右指针视为双链接列表中上一个和下一个指针的同义词。]

让我们以下面的BST为例，它可能会帮助您更好地理解这个问题：我们希望将这个BST转换为一个循环双链接列表。双链表中的每个节点都有一个前导节点和后继节点。对于循环双链表，第一个元素的前一个元素是最后一个元素，最后一个元素的后一个元素是第一个元素。

下图显示了上述BST的循环双链接列表。“head”符号表示它指向的节点是链表中最小的元素。

https://www.lintcode.com/problem/convert-binary-search-tree-to-sorted-doubly-linked-list/description

说明：左：反向输出右：正序输出

我的代码：

class Solution:
    """
    @param root: root of a tree
    @return: head node of a doubly linked list
    """
    def treeToDoublyList(self, root):
        # Write your code here.
        if not root: 
            return None
        
        prev = node(0)
        self.treeToDoublyList(root.left)
        
        if prev is None:
            
            prev = root
        else:
            prev.left = root
            root.right = prev
        
        
        
        
        self.treeToDoublyList(root.right)

Answer 1

给定节点类：

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

...您可以首先定义一个按顺序生成节点的函数：

class Solution:
    def inorder(self, tree):
        if tree.left:
            yield from self.inorder(tree.left)
        yield tree
        if tree.right:
            yield from self.inorder(tree.right)   

然后main函数的实现变成花生：

    def treeToDoublyList(self, root):
        if not root:
            return
        prev = None
        for curr in self.inorder(root):
            # Create double link between prev and curr
            if prev:
                prev.right = curr
            else:
                head = curr
            curr.left = prev
            # Prepare for next iteration
            prev = curr
        # Close the cycle
        curr.right = first
        head.left = curr
        return head

为了测试双链表，您可以再定义两个函数：

    def forward(self, head):
        node = head
        yield node.val
        while node.right != head:
            node = node.right
            yield node.val

    def backward(self, head):
        node = head
        yield node.val
        while node.left != head:
            node = node.left
            yield node.val

按如下方式调用这些函数：

sol = Solution()
# Example tree
tree =  Node(4, 
            Node(2, 
                Node(1), Node(3)
            ),
            Node(5)
        )
res = sol.treeToDoublyList(tree)
print(list(sol.forward(res)))  # [1, 2, 3, 4, 5]
print(list(sol.backward(res)))  # [1, 5, 4, 3, 2]