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

Question

I have a problem of "None does not have .val" in my solution... I wonder how to debug it...

Here is the description

Convert Binary Search Tree to Sorted Doubly Linked List

Convert a BST to a sorted circular doubly-linked list in-place. Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list.]

Let's take the following BST as an example, it may help you understand the problem better:We want to transform this BST into a circular doubly linked list. Each node in a doubly linked list has a predecessor and successor. For a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element.

The figure below shows the circular doubly linked list for the BST above. The "head" symbol means the node it points to is the smallest element of the linked list.

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

Explanation: Left: reverse output Right: positive sequence output

My code:

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)

trincot trincot · Accepted Answer · 2020-11-20T21:38:06

Given the node class:

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

...you could first define a function that yields the nodes in in-order sequence:

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)

Then the implementation of the main function becomes peanuts:

    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

In order to test the doubly linked list, you could define two more functions:

    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

Call these functions as follows:

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]

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

1 Answers