def recoverTree(self, root: TreeNode) -> None:
x = y = pre = None
stack = []
node = root
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
# 先遇到 x or y, pre代表的點不一樣
if pre and pre.val > node.val:
y = node
if x == None:
x = pre
else:
break
pre = node
node = node.right
x.val, y.val = y.val, x.val
Recursive
def recoverTree(self, root: TreeNode) -> None:
def find_swap(node):
nonlocal x, y, pre
if not node: return
find_swap(node.left)
if pre and pre.val > node.val:
y = node
# first swap point
if x == None:
x = pre
# second swap point
else:
return
pre = node
find_swap(node.right)
x = y = pre = None
find_swap(root)
x.val, y.val = y.val, x.val
Morris
def recoverTree(self, root: TreeNode) -> None:
def findPredecessor(node):
pre = node.left
while pre.right and pre.right != node:
pre = pre.right
return pre
cur = root
x = y = pre = None
while cur:
if cur.left:
predecessor = findPredecessor(cur)
if not predecessor.right:
predecessor.right = cur
cur = cur.left
else:
if pre and pre.val > cur.val:
y = cur
if not x:
x = pre
# will casue cycle if break the loop
# else:
# break
predecessor.right = None
pre = cur
cur = cur.right
else:
if pre and pre.val > cur.val:
y = cur
if not x:
x = pre
# will casue cycle if break the loop
#else:
# break
pre = cur
cur = cur.right
x.val, y.val = y.val, x.val
450 Delete Node
1 child, 2 child situation
2 child => find min in right child
delete min in right child
def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
if not root: return None
if root.val < key:
root.right = self.deleteNode(root.right, key)
return root
elif root.val > key:
root.left = self.deleteNode(root.left, key)
return root
else:
if not root.left and not root.right:
return None
elif not root.left:
return root.right
elif not root.right:
return root.left
else:
min_val = self.findMin(root.right)
root.val = min_val
root.right = self.deleteNode(root.right, min_val)
return root
def findMin(self, node):
min_val = 0
while node:
min_val = node.val
node = node.left
return min_val
701 Insert Node in BST
construct the node when root == null, otherwise just pass the node
public TreeNode insertNode(TreeNode root, TreeNode node) {
if (root == null){
return node;
}
if (root.val > node.val){
root.left = insertNode(root.left, node);
}
if (root.val < node.val){
root.right = insertNode(root.right, node);
}
return root;
}
Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
Calling next() will return the next smallest number in the BST.
Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.
Use a stack to store next smallest number
apply addLeft method, add left nodes to stack
public class BSTIterator {
private Stack<TreeNode> s = new Stack<>();
public BSTIterator(TreeNode root) {
addLeft(root);
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return !s.isEmpty();
}
/** @return the next smallest number */
public int next() {
TreeNode tmp = s.pop();
addLeft(tmp.right);
return tmp.val;
}
private void addLeft(TreeNode node){
while(node != null){
s.push(node);
node = node.left;
}
}
}
285 Inorder successor in BST
Given a binary search tree and a node in it, find the in-order successor of that node in the BST.
Note: If the given node has no in-order successor in the tree, return null.
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
if (root == null){
return null;
}
if (root.val <= p.val){
return inorderSuccessor(root.right, p);
}
TreeNode left = inorderSuccessor(root.left, p);
return left == null ? root : left;
}
510 Inorder Successor in BST II
Given a node in a binary search tree, find the in-order successor of that node in the BST. If that node has no in-order successor, return null. The Node has parent attribute
def inorderSuccessor(self, node: 'Node') -> 'Node':
# if successor in right child
if node.right:
node = node.right
while node.left:
node = node.left
return node
# if successor in upper level (this including no successor case)
while node.parent and node.parent.right == node:
node = node.parent
return node.parent
Search Range
Recursion - create helper
public List<Integer> searchRange(TreeNode root, int k1, int k2) {
List<Integer> result = new ArrayList<>();
helper(root, k1, k2, result);
return result;
}
private void helper(TreeNode root, int k1, int k2, List<Integer> result){
if(root == null){
return;
}
if(root.val > k1){
helper(root.left, k1, k2, result);
}
if(root.val >= k1 && root.val <= k2){
result.add(root.val);
}
if(root.val < k2){
helper(root.right, k1, k2, result);
}
}
firstGreaterThanK
if node.data > k, record current node (no right tree on node.left)
public static BstNode<Integer> findFirstGreatThanK(BstNode<Integer> tree, Integer k){
BstNode<Integer> subtree = tree, Result_node = null;
while(tree != null){
if (tree.data > k){
Result_node = tree;
tree = tree.left;
}else{
tree = tree.right;
}
}
return Result_node;
}
230 find Kth smallest element in BST
inorder
private int count;
private int ans;
public int kthSmallest(TreeNode root, int k) {
count = 0;
helper(root, k);
return ans;
}
private void helper(TreeNode node, int k){
if(node == null) return;
if(count < k){
helper(node.left, k);
if(++count == k){
ans = node.val;
return;
}
helper(node.right, k);
}
}
315. Count of Smaller Numbers After Self
You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].
"""
A tree node, with count value represent smaller counts
Traverse from end, build the tree and count number of smaller nodes
"""
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.count = 1 # 小於等於自己的node個數
class Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
if not nums: return []
root = Node(nums[-1])
res = [0]
# starting from last 2nd idx in reverse order
for n in nums[-2::-1]:
count = self.insert(root, n)
res.append(count)
return res[::-1]
def insert(self, node, val):
count = 0
while True:
if val <= node.val:
node.count += 1
if not node.left:
node.left = Node(val)
break
else:
node = node.left
else:
count += node.count
if not node.right:
node.right = Node(val)
break
else:
node = node.right
return count