LeetCode 426. Convert Binary Search Tree to Sorted Doubly Linked List
Explanation: The figure below shows the transformed BST. The solid line indicates the successor relationship, while the dashed line means the predecessor relationship.
Inorder
inorder is a very natural way as in order will make the binary search tree sorted.
"""
# 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 root
res = []
def inorder(node):
if node is None:return
inorder(node.left)
res.append(node)
inorder(node.right)
inorder(root)
for i in range(len(res)-1):
res[i].right = res[i+1]
res[i+1].left = res[i]
res[-1].right = res[0]
res[0].left = res[-1]
return res[0]
Above code’s memory complexity is O(n), in order to have a O(1) memory complexity, we can use the following code
"""
# 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 root
self.prev = dummy = Node(-1)
def inorder(node):
if node is None:return
inorder(node.left)
self.prev.right=node
node.left = self.prev
self.prev = node
inorder(node.right)
inorder(root)
self.prev.right=dummy.right
dummy.right.left = self.prev
print(self.prev.val)
return dummy.right
Another code from here for reference
if not root: return
dummy = Node(0, None, None)
prev = dummy
stack, node = [], root
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
node.left, prev.right, prev = prev, node, node
node = node.right
dummy.right.left, prev.right = prev, dummy.right
return dummy.rightIt can be modified as below
"""
# 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 root
dummy = prev = Node(-1)
stack = []
node = root
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
prev.right = node
node.left = prev
prev = node
node = node.right
head = dummy.right
prev.right = head
head.left = prev
return dummy.right
Be careful the order when connect the head and tail.
postorder
C++ code[1]
Use postorder traversal, the complexity is O(n)
If the BST is (10(6, 1, 8),(20, 15, null))
change it to list, we will get:
1–6–8–10–15–20
We can see that the prev of 10 is the max(1,6,8) and the next of 10 is min(15, 20).
So the idea is:
preorder traverse and get the left max and right min. Then connect it to root.
// return min node and max node in the tree
pair<Node*, Node*> dfs(Node* root) {
if(!root) return {nullptr, nullptr};auto left = dfs(root->left);
auto right = dfs(root->right);// connect
root->left = left.second;
root->right = right.first;
if(left.second) left.second->right = root;
if(right.first) right.first->left = root;return { left.first? left.first : root,
right.second? right.second : root};
}Node* treeToDoublyList(Node* root) {
if(!root) return nullptr;auto p = dfs(root);
// connect head and tail
p.first->left = p.second;
p.second->right = p.first;
return p.first;
}
Reference
