C++で二分木の2番目に小さいノードの値を求める方法

本記事では、特殊な二分木（バイナリツリー）の中から2番目に小さい値を見つけるアルゴリズムを、C++のコード例とともにわかりやすく解説します。

問題の概要

次のような条件を満たす、空ではない特殊な二分木が与えられます。

• 各ノードは「子を2つ持つ」か「子を1つも持たない」かのどちらかである
• ノードが2つの子を持つ場合、そのノードの値は必ず2つの子のうち小さい方の値と等しい

つまり、root.val = min(root.left.val, root.right.val) という関係が常に成り立ちます。

このような二分木が与えられたとき、木全体のすべてのノードの値からなる集合の中で2番目に小さい値を求めてください。該当する値が存在しない場合は -1 を返します。

入力例

例えば、次のような木を考えてみましょう。

{2,2,5,NULL,NULL,5,7}

この場合の出力は 5 になります。最小値は 2、そして2番目に小さい値は 5 だからです。

解き方のアプローチ

この問題は、木を深さ優先探索（DFS）で走査しながら、最小値より大きい値の中で最も小さいものを追跡することで解けます。手順は以下の通りです。

1. TraverseNodes() 関数を定義します。引数としてノード、現在の最小値 min、2番目の候補値 nextMin を受け取ります。
2. ノードが null の場合は何もせずに return します。
3. ノードの値が min より大きい場合：
   • nextMin がまだ -1（未設定）であるか、ノードの値が現在の nextMin より小さければ、nextMin をそのノードの値で更新します。
4. 左の子ノードと右の子ノードに対して再帰的に TraverseNodes() を呼び出します。
5. メイン処理では以下を行います：
   • min をルートの値に設定します（ルートが null の場合は -1）。特殊な二分木の性質上、ルートの値が必ず全体の最小値になるためです。
   • nextMin を -1 で初期化します。
   • TraverseNodes(root, min, nextMin) を呼び出します。
   • nextMin を返します。

C++による実装例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
    public:
        int val;
        TreeNode *left, *right;
        TreeNode(int data){
            val = data;
            left = NULL;
            right = NULL;
    }
};
void insert(TreeNode **root, int val){
    queue<TreeNode*> q;
    q.push(*root);
    while(q.size()){
        TreeNode *temp = q.front();
        q.pop();
        if(!temp->left){
            if(val != NULL)
                temp->left = new TreeNode(val);
            else
                temp->left = new TreeNode(0);
            return;
        }else{
            q.push(temp->left);
        }
        if(!temp->right){
            if(val != NULL)
                temp->right = new TreeNode(val);
            else
                temp->right = new TreeNode(0);
            return;
        }else{
            q.push(temp->right);
        }
    }
}
TreeNode *make_tree(vector<int> v){
    TreeNode *root = new TreeNode(v[0]);
    for(int i = 1; i<v.size(); i++){
        insert(&root, v[i]);
    }
    return root;
}
class Solution {
public:
    int findSecondMinimumValue(TreeNode* root) {
        int min = (root && root->val != 0) ? root->val : -1;
        int nextMin = -1;
        TraverseNodes(root, min, nextMin);
        return nextMin;
    }
    void TraverseNodes(TreeNode* node, int min, int& nextMin) {
        if (!node || node->val == 0) {
            return;
        }
        if (node->val > min) {
            if (nextMin == -1 || node->val < nextMin) {
                nextMin = node->val;
            }
        }
        TraverseNodes(node->left, min, nextMin);
        TraverseNodes(node->right, min, nextMin);
    }
};
main(){
    Solution ob;
    vector<int> v = {2,2,5,NULL,NULL,5,7};
    TreeNode *root = make_tree(v);
    cout << (ob.findSecondMinimumValue(root));
}

実行結果

入力

{2,2,5,NULL,NULL,5,7}

出力

5

計算量について

このアルゴリズムの計算量は以下の通りです。

• 時間計算量： O(n) — 木のすべてのノードを最大1回ずつ訪問するためです。
• 空間計算量： O(h) — 再帰呼び出しのスタックの深さは木の高さ h に依存します。

まとめ

特殊な二分木では親ノードの値が常に子の最小値と一致するため、ルートの値が自動的に全体の最小値になります。この性質を利用すれば、DFSで一度木を走査するだけで「最小値より大きい値のうち最小のもの」、すなわち2番目に小さい値を効率的に求められるのです。すべてのノードの値が同じ場合など、2番目に小さい値が存在しないケースでは -1 が返される点にも注意しましょう。