leetcode convert binary search tree to sorted doubly linked list
"""
# Definition for a Node.
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
"""
class Solution:
def treeToDoublyList(self, root: 'Node') -> 'Node':
if not root:
return None
node_values = []
self.get_node_values(root, node_values)
first_node = Node(node_values[0])
prev = first_node
for value in node_values[1:]:
new_node = Node(value)
new_node.left = prev
prev.right = new_node
prev = new_node
prev.right = first_node
first_node.left = prev
return first_node
def get_node_values(self, root, results):
if not root:
return
self.get_node_values(root.left, results)
results.append(root.val)
self.get_node_values(root.right, results)