426. Convert Binary Search Tree to Sorted Doubly Linked List

Problem Statement

link: LeetCode.cn LeetCode Convert a Binary Search Tree to a sorted Circular Doubly-Linked List in place.

You can think of the left and right pointers as synonymous to the predecessor and successor pointers in a doubly-linked list. 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.

We want to do the transformation in place. After the transformation, the left pointer of the tree node should point to its predecessor, and the right pointer should point to its successor. You should return the pointer to the smallest element of the linked list.

Example:

Input: root = [4,2,5,1,3] Output: [1,2,3,4,5]

Input: root = [2,1,3] Output: [1,2,3]

Constraints: The number of nodes in the tree is in the range [0, 2000]. -1000 <= Node.val <= 1000 All the values of the tree are unique.

Solution Approach

The solution involves performing an in-order traversal of the Binary Search Tree (BST) to connect nodes into a sorted doubly linked list, with the first and last nodes linked circularly.

Algorithm

1. In-Order Traversal: The solution uses in-order traversal to process the BST nodes in ascending order, ensuring the resulting linked list is sorted.
2. Linking Nodes: During the traversal, each node is connected to its predecessor and successor, effectively converting the BST into a doubly linked list.
3. Circular Linking: After traversal, the first and last nodes are linked to make the list circular, with the first node’s left pointer pointing to the last node and the last node’s right pointer pointing to the first node.

Implement

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

class Solution:
    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':
        #left root right
        if not root:
            return None
        self.first = None
        self.last = None
        self.inorder_link(root)
        
        self.first.left = self.last
        self.last.right = self.first
        return self.first
    def inorder_link(self, node):
        if node:
            self.inorder_link(node.left)
            if not self.last:
                self.first = node
            else:
                node.left = self.last
                self.last.right = node
            self.last = node
            self.inorder_link(node.right) 

    
    

Twitter  facebook  Email