二分木の剪枝処理

値が0で子ノードを持たないノードを削除する再帰アルゴリズムです。

public TreeNode trimZeroNodes(TreeNode node) {
    if (node == null) return null;
    node.left = trimZeroNodes(node.left);
    node.right = trimZeroNodes(node.right);
    if (node.value == 0 && node.left == null && node.right == null) {
        return null;
    }
    return node;
}

二分木のシリアライズとデシリアライズ

前順走査を用いたシリアライズとキューを用いたデシリアライズの実装例です。

public class TreeSerializer {
    private StringBuilder serializedData = new StringBuilder();
    
    public String serialize(TreeNode node) {
        traverse(node);
        return serializedData.toString();
    }
    
    private void traverse(TreeNode node) {
        if (node == null) {
            serializedData.append("null,");
            return;
        }
        serializedData.append(node.value).append(",");
        traverse(node.left);
        traverse(node.right);
    }
    
    public TreeNode deserialize(String data) {
        String[] tokens = data.split(",");
        Queue<String> queue = new LinkedList<>(Arrays.asList(tokens));
        return buildTree(queue);
    }
    
    private TreeNode buildTree(Queue<String> queue) {
        String token = queue.poll();
        if ("null".equals(token)) return null;
        TreeNode node = new TreeNode(Integer.parseInt(token));
        node.left = buildTree(queue);
        node.right = buildTree(queue);
        return node;
    }
}

ルートから葉へのパスの数値合計

各ノードの値を桁として扱い、パスの合計を計算する再帰アルゴリズムです。

public class PathSumCalculator {
    public int calculatePathSum(TreeNode node) {
        return computeSum(node, 0);
    }
    
    private int computeSum(TreeNode node, int current) {
        if (node == null) return 0;
        int total = current * 10 + node.value;
        if (node.left == null && node.right == null) return total;
        return computeSum(node.left, total) + computeSum(node.right, total);
    }
}

パスの合計が特定値となる経路数

二分木内でパスの合計が指定値となる経路の数を数えるアルゴリズムです。

public class PathCounter {
    private int result = 0;
    
    public int countValidPaths(TreeNode node, int target) {
        if (node == null) return 0;
        checkPath(node, target);
        countValidPaths(node.left, target);
        countValidPaths(node.right, target);
        return result;
    }
    
    private void checkPath(TreeNode node, int remaining) {
        if (node == null) return;
        if (node.value == remaining) result++;
        checkPath(node.left, remaining - node.value);
        checkPath(node.right, remaining - node.value);
    }
}

最大パス和の計算

二分木内の任意のパスの最大和を求めるアルゴリズムです。

public class MaxPathFinder {
    private int globalMax = Integer.MIN_VALUE;
    
    public int findMaximumPath(TreeNode node) {
        computeMax(node);
        return globalMax;
    }
    
    private int computeMax(TreeNode node) {
        if (node == null) return 0;
        int left = Math.max(0, computeMax(node.left));
        int right = Math.max(0, computeMax(node.right));
        globalMax = Math.max(globalMax, left + right + node.value);
        return node.value + Math.max(left, right);
    }
}

二分探索木の順序後続ノード検索

中順走査での指定ノードの次ノードを検索するアルゴリズムです。

public class InorderSuccessor {
    private TreeNode successor = null;
    private boolean found = false;
    
    public TreeNode findSuccessor(TreeNode root, TreeNode target) {
        search(root, target);
        return successor;
    }
    
    private void search(TreeNode node, TreeNode target) {
        if (node == null || successor != null) return;
        search(node.left, target);
        if (found && successor == null) {
            successor = node;
            return;
        }
        if (node == target) found = true;
        search(node.right, target);
    }
}

二分探索木の値変換

各ノードの値を右部分木の合計値に置き換えるアルゴリズムです。

public class ValueTransformer {
    private int cumulativeSum = 0;
    
    public TreeNode transformBST(TreeNode node) {
        reverseInorder(node);
        return node;
    }
    
    private void reverseInorder(TreeNode node) {
        if (node == null) return;
        reverseInorder(node.right);
        cumulativeSum += node.value;
        node.value = cumulativeSum;
        reverseInorder(node.left);
    }
}

二分探索木イテレータ

中順走査順に要素を取得するイテレータ実装です。

public class BSTIterator {
    private TreeNode current;
    
    public BSTIterator(TreeNode root) {
        current = new TreeNode(-1);
        TreeNode tail = current;
        inorderFlatten(root, tail);
    }
    
    private void inorderFlatten(TreeNode node, TreeNode tail) {
        if (node == null) return;
        inorderFlatten(node.left, tail);
        tail.right = node;
        tail = node;
        node.left = null;
        inorderFlatten(node.right, tail);
    }
    
    public int next() {
        current = current.right;
        return current.value;
    }
    
    public boolean hasNext() {
        return current.right != null;
    }
}

スライディングウィンドウと多重集合の応用

値とインデックスの差が指定範囲内にある要素を検索するアルゴリズムです。

public boolean checkNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
    TreeSet<Long> window = new TreeSet<>();
    window.add(Long.MAX_VALUE);
    window.add(Long.MIN_VALUE);
    
    for (int i = 0, j = 0; i < nums.length; i++) {
        if (i - j > indexDiff) {
            window.remove((long) nums[j++]);
        }
        long num = nums[i];
        Long ceiling = window.ceiling(num);
        Long floor = window.floor(num);
        if (ceiling != null && ceiling - num <= valueDiff) return true;
        if (floor != null && num - floor <= valueDiff) return true;
        window.add(num);
    }
    return false;
}