BST — 實戰題解

# python
# LC 776 - Split BST
# IDEA: root <= target -> root heads the small tree; split its right child and keep the small part;
#       root > target  -> root heads the big tree; split its left child and keep the big part
# time = O(h), space = O(h)
def splitBST(root, target):
    if not root:
        return [None, None]                 # [<= target, > target]
    if root.val <= target:
        small, big = splitBST(root.right, target)
        root.right = small                  # the part of the right subtree that stays with root
        return [root, big]
    small, big = splitBST(root.left, target)
    root.left = big                         # the part of the left subtree that stays with root
    return [small, root]

// java
// LC 776 - Split BST
// IDEA: split only the child that straddles target, reattach the half that belongs with root
// time = O(h), space = O(h)
public TreeNode[] splitBST(TreeNode root, int target) {
    if (root == null) {
        return new TreeNode[]{null, null};
    }
    if (root.val <= target) {
        TreeNode[] split = splitBST(root.right, target);
        root.right = split[0];
        return new TreeNode[]{root, split[1]};
    }
    TreeNode[] split = splitBST(root.left, target);
    root.left = split[1];
    return new TreeNode[]{split[0], root};
}

[4,2,6,1,3,5,7], target = 2
at 4: 4 > 2   -> split 4.left (2); 4 keeps the big half of it
at 2: 2 <= 2  -> split 2.right (3); 2 keeps the small half of it
at 3: 3 > 2   -> split 3.left (null) -> [null, null]; return [null, 3]
back at 2: 2.right = null           -> return [2, 3]
back at 4: 4.left = 3               -> return [2, 4]
small tree [2,1]          big tree [4,3,6,null,null,5,7]

# python
# IDEA: Template 3b's pruning; add the in-range values instead of reattaching them
# time = O(n), space = O(h)
# LC 938 - Range Sum of BST
def rangeSumBST(root, low, high):
    if not root:
        return 0
    if root.val < low:                    # nothing on the left can be in range
        return rangeSumBST(root.right, low, high)
    if root.val > high:                   # nothing on the right can be in range
        return rangeSumBST(root.left, low, high)
    return (root.val
            + rangeSumBST(root.left, low, high)
            + rangeSumBST(root.right, low, high))

# python
# LC 449 - Serialize and Deserialize BST
# IDEA: serialize = preorder values only; deserialize = rebuild with (low, high) bounds:
#       the next value starts this subtree iff it fits the interval, else this subtree is empty
# time = O(n), space = O(n)
from collections import deque

class Codec:
    def serialize(self, root):
        vals = []

        def preorder(node):
            if not node:
                return
            vals.append(str(node.val))
            preorder(node.left)
            preorder(node.right)

        preorder(root)
        return ",".join(vals)

    def deserialize(self, data):
        vals = deque(int(x) for x in data.split(",")) if data else deque()

        def build(low, high):
            if not vals or not (low < vals[0] < high):
                return None                    # the next value belongs to an ancestor
            node = TreeNode(vals.popleft())
            node.left = build(low, node.val)
            node.right = build(node.val, high)
            return node

        return build(float("-inf"), float("inf"))

# python
# IDEA: reverse in-order (right, node, left) with a running sum of the values seen so far
# time = O(n), space = O(h)
# LC 538 - Convert BST to Greater Tree
class Solution(object):
    def convertBST(self, root):
        self.running = 0

        def reverse_inorder(node):
            if not node:
                return
            reverse_inorder(node.right)   # larger values first
            self.running += node.val
            node.val = self.running
            reverse_inorder(node.left)

        reverse_inorder(root)
        return root