Leetcode:convert-binary-search-tree-to-sorted-doubly-linked-list

Question

在我的解决方案中，我遇到了“没有人没有.val”的问题.我想知道怎么调试..。

下面是描述

1. 将二进制搜索树转换为排序双链接列表

将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

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

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)   

然后，主要功能的实现就变得微不足道：

    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]