1. 二分探索木における最小絶対差の取得

二分探索木（BST）の性質として、中序巡回（In-order Traversal）を行うと、ノードの値を昇順で取得できるという特徴があります。この性質を利用することで、隣接するノード間の差分を比較し、最小絶対差を効率的に求めることが可能です。

ポインタ prevNode を使用して、常に現在のノード currNode の直前の値を保持することで、1回の走査で最小値を更新していきます。

class Solution {
private:
    int minGap = INT_MAX;
    TreeNode* prevNode = nullptr;

    void inOrder(TreeNode* curr) {
        if (!curr) return;

        // 左部分木の探索
        inOrder(curr->left);

        // 現在のノードと直前のノードの差分を計算
        if (prevNode) {
            minGap = min(minGap, curr->val - prevNode->val);
        }
        prevNode = curr;

        // 右部分木の探索
        inOrder(curr->right);
    }

public:
    int getMinimumDifference(TreeNode* root) {
        inOrder(root);
        return minGap;
    }
};

2. 二分探索木における最頻値の探索

BSTにおいて出現頻度が最も高い値（最頻値）を求める際、ハッシュマップを使用する方法と、空間計算量を抑えるための2ポインタ法があります。

ハッシュマップを利用した頻度集計

まず全ノードを走査してマップに頻度を記録し、その後に最大頻度を持つ要素を抽出します。

class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        unordered_map<int, int> freqMap;
        int maxFreq = 0;
        vector<int> result;

        traverse(root, freqMap, maxFreq);

        for (auto const& [val, count] : freqMap) {
            if (count == maxFreq) {
                result.push_back(val);
            }
        }
        return result;
    }

private:
    void traverse(TreeNode* node, unordered_map<int, int>& freqMap, int& maxFreq) {
        if (!node) return;
        
        traverse(node->left, freqMap, maxFreq);
        freqMap[node->val]++;
        maxFreq = max(maxFreq, freqMap[node->val]);
        traverse(node->right, freqMap, maxFreq);
    }
};

最適化された2ポインタ法

中序巡回中に「現在の値の出現回数」をカウントし、最大頻度が更新された場合に結果リストをリセットすることで、追加のデータ構造（マップ）なしで解くことができます。

class Solution {
private:
    int currentFreq = 0;
    int maxFreq = 0;
    TreeNode* lastNode = nullptr;
    vector<int> modes;

    void findModesInOrder(TreeNode* curr) {
        if (!curr) return;

        findModesInOrder(curr->left);

        // 頻度のカウントロジック
        if (!lastNode || lastNode->val != curr->val) {
            currentFreq = 1;
        } else {
            currentFreq++;
        }

        // 最大頻度の更新と結果の格納
        if (currentFreq == maxFreq) {
            modes.push_back(curr->val);
        } else if (currentFreq > maxFreq) {
            maxFreq = currentFreq;
            modes.clear();
            modes.push_back(curr->val);
        }

        lastNode = curr;
        findModesInOrder(curr->right);
    }

public:
    vector<int> findMode(TreeNode* root) {
        findModesInOrder(root);
        return modes;
    }
};

3. 二分木における最近共通祖先（LCA）

指定された2つのノード p と q の最近共通祖先を探すには、後序巡回（Post-order Traversal）を用いるのが適切です。下から上へと探索結果を返すことで、最初に両方のノードが見つかった分岐点が共通祖先となります。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // ベースケース：ノードが見つかったか終端に達した場合
        if (root == nullptr || root == p || root == q) {
            return root;
        }

        // 左右の部分木を再帰的に探索
        TreeNode* leftSide = lowestCommonAncestor(root->left, p, q);
        TreeNode* rightSide = lowestCommonAncestor(root->right, p, q);

        // 左右両方からノードが返ってきた場合、現在のノードが共通祖先
        if (leftSide && rightSide) {
            return root;
        }
        
        // 片方からのみ返ってきた場合、その結果をさらに上に伝える
        return leftSide ? leftSide : rightSide;
    }
};