def flatten(self, root: TreeNode) -> None:
if not root: return
node = root
while node:
if node.left:
rightMost = node.left
while rightMost.right:
rightMost = rightMost.right
rightMost.right = node.right
node.right = node.left
node.left = None
node = node.right
106t Convert Sorted LinkedList to Balanced BST
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
Divide and Conquer
public TreeNode sortedListToBST(ListNode head) {
if (head == null){
return null;
}
return BSTHelper(head, null);
}
public TreeNode BSTHelper(ListNode head, ListNode tail) {
if (head == tail){
return null;
}
// let slow goes to middle point
ListNode slow = head, fast = head;
while(fast.next != tail && fast.next.next != tail){
slow = slow.next;
fast = fast.next.next;
}
TreeNode left = BSTHelper(head, slow);
TreeNode right = BSTHelper(slow.next, tail);
TreeNode root = new TreeNode(slow.val);
root.left = left;
root.right = right;
return root;
}
426 Convert BST to double 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.並且首尾相連
private Node pre;
public Node treeToDoublyList(Node root) {
if(root == null) return null;
Node dummy = new Node(0);
pre = dummy;
helper(root);
// now the "pre" is the tail node
// connect head and tail
pre.right = dummy.right;
dummy.right.left = pre;
return dummy.right;
}
private void helper(Node node){
if(node == null) return;
helper(node.left);
pre.right = node; // 同時將dummy.right 指向 head node
node.left = pre;
pre = node; // 這裏dummy 不跟著變化
helper(node.right);
}
"""
inorder traverse
current node and tail node 之間更新
需要兩個pointer紀錄head and tail
最後head and tail連起來
"""
class Solution:
def treeToDoublyList(self, root: 'Node') -> 'Node':
if not root: return None
self.head, self.tail = None, None
self.helper(root)
self.tail.right = self.head
self.head.left = self.tail
return self.head
def helper(self, node):
if not node: return
self.helper(node.left)
if self.tail:
self.tail.right = node
node.left = self.tail
else:
# 只會更新一次, 在head的時候
self.head = node
self.tail = node
self.helper(node.right)
