BST — LeetCode 實作範例

# LC 449 Serialize and Deserialize BST
# V0
# IDEA : BFS + queue op
class Codec:
    def serialize(self, root):
        if not root:
            return '{}'

        res = [root.val]
        q = [root]

        while q:
            new_q = []
            for i in range(len(q)):
                tmp = q.pop(0)
                if tmp.left:
                    q.append(tmp.left)
                    res.extend( [tmp.left.val] )
                else:
                    res.append('#')
                if tmp.right:
                    q.append(tmp.right)
                    res.extend( [tmp.right.val] )
                else:
                    res.append('#')

        while res and res[-1] == '#':
                    res.pop()

        return '{' + ','.join(map(str, res)) + '}' 


    def deserialize(self, data):
        if data == '{}':
            return

        nodes = [ TreeNode(x) for x in data[1:-1].split(",") ]
        root = nodes.pop(0)
        p = [root]
        while p:
            new_p = []
            for n in p:
                if nodes:
                    left_node = nodes.pop(0)
                    if left_node.val != '#':
                        n.left = left_node
                        new_p.append(n.left)
                    else:
                        n.left = None
                if nodes:
                    right_node = nodes.pop(0)
                    if right_node.val != '#':
                        n.right = right_node
                        new_p.append(n.right)
                    else:
                        n.right = None
            p = new_p 
             
        return root

# V1
# IDEA : same as LC 297
# https://leetcode.com/problems/serialize-and-deserialize-bst/discuss/93283/Python-solution-using-BST-property
class Codec:

    def serialize(self, root):
        vals = []
        self._preorder(root, vals)
        return ','.join(vals)
        
    def _preorder(self, node, vals):
        if node:
            vals.append(str(node.val))
            self._preorder(node.left, vals)
            self._preorder(node.right, vals)
        
    def deserialize(self, data):
        vals = collections.deque(map(int, data.split(','))) if data else []
        return self._build(vals, -float('inf'), float('inf'))

    def _build(self, vals, minVal, maxVal):
        if vals and minVal < vals[0] < maxVal:
            val = vals.popleft()
            root = TreeNode(val)
            root.left = self._build(vals, minVal, val)
            root.right = self._build(vals, val, maxVal)
            return root
        else:
            return None

Return value: TreeNode[2]
  res[0] → BST with all values ≤ target
  res[1] → BST with all values > target

Case 1: root.val <= target
  → root belongs to LEFT partition (res[0])
  → But root.right may contain nodes > target
  → So SPLIT root.right, reconnect the pieces

Case 2: root.val > target
  → root belongs to RIGHT partition (res[1])
  → But root.left may contain nodes <= target
  → So SPLIT root.left, reconnect the pieces

Input:        target = 2
         4
        / \
       2   6
      / \ / \
     1  3 5  7

Step 1: root=4, val=4 > target=2 → root goes to RIGHT partition
        Split root.left (the subtree rooted at 2)

Step 2: root=2, val=2 <= target=2 → root goes to LEFT partition
        Split root.right (the subtree rooted at 3)

Step 3: root=3, val=3 > target=2 → root goes to RIGHT partition
        Split root.left (null) → returns [null, null]
        root.left = null (from split[1])
        Return [null, 3]

Back to Step 2: split of node 2's right returned [null, 3]
        node 2's right = split[0] = null  (was 3, now detached)
        Return [2→(left:1, right:null), 3]

Back to Step 1: split of node 4's left returned [2, 3]
        node 4's left = split[1] = 3  (reconnect!)
        Return [2, 4→(left:3, right:6)]

Result:
  res[0] (≤ 2):     res[1] (> 2):
       2                  4
      /                  / \
     1                  3   6
                           / \
                          5   7

When root.val <= target and we split root.right:
  split[0] = nodes from right subtree that are still <= target
  split[1] = nodes from right subtree that are > target

  root.right = split[0]   ← keep the small ones attached to root
  return [root, split[1]] ← root is left partition, split[1] is right partition

When root.val > target and we split root.left:
  split[0] = nodes from left subtree that are <= target
  split[1] = nodes from left subtree that are > target

  root.left = split[1]    ← keep the big ones attached to root
  return [split[0], root] ← split[0] is left partition, root is right partition

# LC 776 Split BST
class Solution(object):
    def splitBST(self, root, V):
        if not root:
            return None, None
        # root belongs to LEFT partition
        elif root.val <= V:
            result = self.splitBST(root.right, V)
            root.right = result[0]  # keep <= V part
            return root, result[1]  # [smallTree, bigTree]
        # root belongs to RIGHT partition
        else:
            result = self.splitBST(root.left, V)
            root.left = result[1]   # keep > V part
            return result[0], root  # [smallTree, bigTree]

// LC 776 Split BST
// Time: O(H), Space: O(H) where H = height of BST
public TreeNode[] splitBST(TreeNode root, int target) {
    if (root == null) {
        return new TreeNode[]{null, null};
    }

    if (root.val <= target) {
        // root goes to LEFT partition (<=target)
        TreeNode[] split = splitBST(root.right, target);
        root.right = split[0];          // reconnect small part
        return new TreeNode[]{root, split[1]};
    } else {
        // root goes to RIGHT partition (>target)
        TreeNode[] split = splitBST(root.left, target);
        root.left = split[1];           // reconnect big part
        return new TreeNode[]{split[0], root};
    }
}

# LC 173. Binary Search Tree Iterator
# IDEA : STACK + tree
class BSTIterator(object):
    def __init__(self, root):
        """
        :type root: TreeNode
        """
        self.stack = []
        self.inOrder(root)
    
    def inOrder(self, root):
        if not root:
            return
        """
        NOTE !!! how we do inorder traversal here

        irOrder : left -> root -> right
        """
        self.inOrder(root.left)
        self.stack.append(root.val)
        self.inOrder(root.right)
    
    def hasNext(self):
        """
        :rtype: bool
        """
        return len(self.stack) > 0

    def next(self):
        """
        :rtype: int
        """
        return self.stack.pop(0)  # NOTE here

# LC 98 Validate Binary Search Tree
# IDEA : BFS
#  -> trick : we make sure current tree and all of sub tree are valid BST
#   -> not only compare tmp.val with tmp.left.val, tmp.right.val,
#   -> but we need compare if tmp.left.val is SMALLER then `previous node val`
#   -> but we need compare if tmp.right.val is BIGGER then `previous node val`
class Solution(object):
    def isValidBST(self, root):
        if not root:
            return True
        _min = -float('inf')
        _max = float('inf')
        ### NOTE : we set q like below
        q = [[root, _min, _max]]
        while q:
            for i in range(len(q)):
                tmp, _min, _max = q.pop(0)
                if tmp.left:
                    """
                    ### NOTE : below condition
                    ### NOTE : we compare "tmp.left.val" with others (BEFORE we visit tmp.left)
                    """
                    if tmp.left.val >= tmp.val or tmp.left.val <= _min:
                        return False
                    ### NOTE : we append tmp.val as _max
                    q.append([tmp.left, _min, tmp.val])
                if tmp.right:
                    """
                    ### NOTE : below condition
                    ### NOTE : we compare "tmp.right.val" with others (BEFORE we visit tmp.right)
                    """
                    if tmp.right.val <= tmp.val or tmp.right.val >= _max:
                        return False
                    ### NOTE : we append tmp.val as _min
                    q.append([tmp.right, tmp.val, _max])
        return True

def has_path_sum(root, target_sum):
    """
    Check if root-to-leaf path exists with given sum
    Time: O(n), Space: O(h)
    """
    if not root:
        return False

    # Leaf node check
    if not root.left and not root.right:
        return root.val == target_sum

    # Recurse with reduced sum
    remaining = target_sum - root.val
    return (has_path_sum(root.left, remaining) or
            has_path_sum(root.right, remaining))

def path_sum(root, target_sum):
    """
    Find all root-to-leaf paths with given sum
    Uses backtracking to track current path
    Time: O(n), Space: O(h)
    """
    result = []

    def dfs(node, remaining, path):
        if not node:
            return

        # Add current node to path
        path.append(node.val)

        # Check if leaf with target sum
        if not node.left and not node.right and remaining == node.val:
            result.append(path[:])  # Deep copy

        # Recurse on children
        new_remaining = remaining - node.val
        dfs(node.left, new_remaining, path)
        dfs(node.right, new_remaining, path)

        # Backtrack
        path.pop()

    dfs(root, target_sum, [])
    return result

def binary_tree_paths(root):
    """
    Find all root-to-leaf paths as strings
    Time: O(n), Space: O(h)
    """
    if not root:
        return []

    result = []

    def dfs(node, path):
        if not node:
            return

        # Add current node to path string
        path += str(node.val)

        # Leaf node - add complete path
        if not node.left and not node.right:
            result.append(path)
            return

        # Continue path with arrow
        path += "->"
        dfs(node.left, path)
        dfs(node.right, path)

    dfs(root, "")
    return result

def sum_numbers(root):
    """
    Sum all numbers formed by root-to-leaf paths
    Example: 1->2->3 represents 123
    Time: O(n), Space: O(h)
    """
    def dfs(node, current_sum):
        if not node:
            return 0

        # Build number: current_sum * 10 + node.val
        current_sum = current_sum * 10 + node.val

        # Leaf node - return the number
        if not node.left and not node.right:
            return current_sum

        # Sum from both subtrees
        return dfs(node.left, current_sum) + dfs(node.right, current_sum)

    return dfs(root, 0)

def max_path_sum(root):
    """
    Find maximum path sum (any node to any node)
    Uses global variable to track maximum
    Time: O(n), Space: O(h)
    """
    max_sum = float('-inf')

    def dfs(node):
        nonlocal max_sum

        if not node:
            return 0

        # Get max contribution from left and right
        # Use max(0, ...) to ignore negative paths
        left_max = max(0, dfs(node.left))
        right_max = max(0, dfs(node.right))

        # Update global max with path through current node
        path_sum = node.val + left_max + right_max
        max_sum = max(max_sum, path_sum)

        # Return max path going through this node (one side only)
        return node.val + max(left_max, right_max)

    dfs(root)
    return max_sum

    1
     \
      2      <-- valid input; path 1 -> 2 -> 3 -> 4 has length 4
     /
    3
     \
      4

# python
# LC 298 - Binary Tree Longest Consecutive Sequence
# IDEA: TOP-DOWN DFS, pass (parent_val, current_len) downward
# time = O(n), each node visited once
# space = O(h), h = tree height (recursion stack)
class Solution(object):
    def longestConsecutive(self, root):
        if not root:
            return 0

        self.max_len = 0

        def dfs(node, parent_val, cur_len):
            if not node:
                return

            # extend the streak, or restart it at this node
            if node.val == parent_val + 1:
                cur_len += 1
            else:
                cur_len = 1

            self.max_len = max(self.max_len, cur_len)

            # NOTE: pass node.val down as the NEW parent value
            dfs(node.left, node.val, cur_len)
            dfs(node.right, node.val, cur_len)

        # trick: seed with (root.val - 1, 0) so root always counts as length 1
        dfs(root, root.val - 1, 0)
        return self.max_len

// java
// LC 298 - Binary Tree Longest Consecutive Sequence
// IDEA: TOP-DOWN DFS
// time = O(n), space = O(h)
class Solution {
    private int maxLen = 0;

    public int longestConsecutive(TreeNode root) {
        if (root == null) return 0;
        dfs(root, root.val - 1, 0);
        return maxLen;
    }

    private void dfs(TreeNode node, int parentVal, int curLen) {
        if (node == null) return;
        curLen = (node.val == parentVal + 1) ? curLen + 1 : 1;
        maxLen = Math.max(maxLen, curLen);
        dfs(node.left, node.val, curLen);
        dfs(node.right, node.val, curLen);
    }
}

# python
# IDEA: POST-ORDER DFS, return "longest consecutive path STARTING at this node"
# time = O(n), space = O(h)
class Solution(object):
    def longestConsecutive(self, root):
        self.max_len = 0

        def helper(node):
            if not node:
                return 0

            left_len = helper(node.left)
            right_len = helper(node.right)

            cur_len = 1
            # NOTE: only take the child's length if the child continues the streak
            if node.left and node.left.val == node.val + 1:
                cur_len = max(cur_len, left_len + 1)
            if node.right and node.right.val == node.val + 1:
                cur_len = max(cur_len, right_len + 1)

            self.max_len = max(self.max_len, cur_len)
            return cur_len          # <-- ONE side only, never left + right

        helper(root)
        return self.max_len

# python
# IDEA: DFS with explicit stack; the streak length travels WITH the node
# time = O(n), space = O(n)
class Solution(object):
    def longestConsecutive(self, root):
        if not root:
            return 0

        stack = [(root, 1)]
        max_len = 1
        while stack:
            node, path_len = stack.pop()
            for child in (node.left, node.right):
                if child:
                    new_len = path_len + 1 if child.val == node.val + 1 else 1
                    max_len = max(max_len, new_len)
                    stack.append((child, new_len))

        return max_len

   1
    \
     3
    / \
   2   4
        \
         5

dfs(1, parent=0, len=0)   -> 1 == 0+1  -> len=1   max=1
  dfs(3, parent=1, len=1) -> 3 != 1+1  -> len=1   max=1   (streak breaks)
    dfs(2, parent=3, len=1) -> 2 != 4  -> len=1   max=1
    dfs(4, parent=3, len=1) -> 4 == 3+1-> len=2   max=2
      dfs(5, parent=4, len=2) -> 5 == 5-> len=3   max=3   <-- answer

# 🚫 WRONG
def helper(self, root):
    if not root:
        return "#"
    _left  = self.helper(root.left)
    _right = self.helper(root.right)
    path = "{}-{}-{}".format(root.val, _left, _right)   # <-- the bug
    self.p_map[path] = 1
    return path

   3
  / \
 9   4
      \
       5

serialize(3) = "3-9-#-#-4-#-5-#-#"
split         = [3, 9, #, #, 4, #, 5, #, #]
                       ^^^^^^^^
   `9` and `4` are SIBLINGS — no edge between them.
   `4` and `5` are a real edge but they are separated by `#`s.
   The linear scan `_list[i] == _list[i-1] + 1` is scanning a
   pre-order dump, NOT a path. It cannot recover the answer.

def path_sum_3(root, target_sum):
    """
    Count paths with given sum (not necessarily root-to-leaf)
    Uses prefix sum technique with hash map
    Time: O(n), Space: O(n)
    """
    from collections import defaultdict

    def dfs(node, current_sum, prefix_sums):
        if not node:
            return 0

        # Update current sum
        current_sum += node.val

        # Count paths ending at current node
        # If (current_sum - target_sum) exists, we found path(s)
        count = prefix_sums[current_sum - target_sum]

        # Add current sum to prefix map
        prefix_sums[current_sum] += 1

        # Recurse on children
        count += dfs(node.left, current_sum, prefix_sums)
        count += dfs(node.right, current_sum, prefix_sums)

        # Backtrack: remove current sum from map
        prefix_sums[current_sum] -= 1

        return count

    # Initialize with 0 sum (for paths starting from root)
    prefix_sums = defaultdict(int)
    prefix_sums[0] = 1

    return dfs(root, 0, prefix_sums)

// Pattern 7.1: Simple Path Sum (LC 112)
public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) return false;

    // Leaf node check
    if (root.left == null && root.right == null) {
        return root.val == targetSum;
    }

    int remaining = targetSum - root.val;
    return hasPathSum(root.left, remaining) ||
           hasPathSum(root.right, remaining);
}

// Pattern 7.2: Path Sum II (LC 113)
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
    List<List<Integer>> result = new ArrayList<>();
    dfs(root, targetSum, new ArrayList<>(), result);
    return result;
}

private void dfs(TreeNode node, int remaining,
                 List<Integer> path, List<List<Integer>> result) {
    if (node == null) return;

    path.add(node.val);

    if (node.left == null && node.right == null && remaining == node.val) {
        result.add(new ArrayList<>(path));
    }

    int newRemaining = remaining - node.val;
    dfs(node.left, newRemaining, path, result);
    dfs(node.right, newRemaining, path, result);

    path.remove(path.size() - 1);  // Backtrack
}

// Pattern 7.5: Maximum Path Sum (LC 124)
private int maxSum = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
    dfs(root);
    return maxSum;
}

private int dfs(TreeNode node) {
    if (node == null) return 0;

    int leftMax = Math.max(0, dfs(node.left));
    int rightMax = Math.max(0, dfs(node.right));

    maxSum = Math.max(maxSum, node.val + leftMax + rightMax);

    return node.val + Math.max(leftMax, rightMax);
}

// Pattern 7.7: Path Sum III (LC 437)
public int pathSum(TreeNode root, int targetSum) {
    Map<Long, Integer> prefixSums = new HashMap<>();
    prefixSums.put(0L, 1);
    return dfs(root, 0L, targetSum, prefixSums);
}

private int dfs(TreeNode node, long currentSum, int target,
                Map<Long, Integer> prefixSums) {
    if (node == null) return 0;

    currentSum += node.val;
    int count = prefixSums.getOrDefault(currentSum - target, 0);

    prefixSums.put(currentSum, prefixSums.getOrDefault(currentSum, 0) + 1);

    count += dfs(node.left, currentSum, target, prefixSums);
    count += dfs(node.right, currentSum, target, prefixSums);

    prefixSums.put(currentSum, prefixSums.get(currentSum) - 1);

    return count;
}

# BAD: Doesn't verify it's a leaf
if root.val == target:
    return True

# GOOD: Check both children are None
if not root.left and not root.right and root.val == target:
    return True

# BAD: Path grows indefinitely
def dfs(node, path):
    path.append(node.val)
    dfs(node.left, path)

# GOOD: Remove after recursion
def dfs(node, path):
    path.append(node.val)
    dfs(node.left, path)
    path.pop()

# BAD: All results reference same list
result.append(path)

# GOOD: Create deep copy
result.append(path[:])  # or list(path)

# BAD: Includes both subtrees in return
def dfs(node):
    left = dfs(node.left)
    right = dfs(node.right)
    return node.val + left + right  # Wrong!

# GOOD: Return one path only
return node.val + max(left, right)

# BAD: Negative paths reduce maximum
left_max = dfs(node.left)

# GOOD: Ignore negative contributions
left_max = max(0, dfs(node.left))