C++で二分木の境界を反時計回りに求める方法

問題の概要

二分木が与えられたとき、根（ルート）から開始して反時計回りに境界（バウンダリ）の値をすべて求めます。境界には左境界・葉ノード・右境界が含まれますが、重複するノードは1度だけ出力します。

• 左境界：根から最も左側にあるノードまでの経路
• 右境界：根から最も右側にあるノードまでの経路
• 根に左部分木（または右部分木）がない場合、根そのものが左境界（または右境界）になります

たとえば、次のような二分木が入力として与えられたとします。

この場合の出力は [1, 2, 4, 7, 8, 9, 10, 6, 3] となります。

解法のアプローチ

この問題は、処理を次の3つの役割に分けて考えるとシンプルになります。

• 左境界の収集：根から下へ向かって、可能な限り左側の子を優先して辿る
• 葉ノードの収集：木全体を走査し、子を持たないノードを左から順に集める
• 右境界の収集：可能な限り右側の子を優先して辿り、結果は下から上へ（逆順）に追加する

具体的な手順は以下のとおりです。

1. 結果を格納する配列 ret を用意する
2. leftBoundary()：ノードを受け取る関数を定義する
   ・ノードがNULL、または葉ノードの場合は何もせず戻る
   ・ノードの値を ret に追加する
   ・左の子が存在すれば leftBoundary(左の子) を呼び出し、存在しなければ leftBoundary(右の子) を呼び出す
3. rightBoundary()：ノードを受け取る関数を定義する
   ・ノードがNULL、または葉ノードの場合は何もせず戻る
   ・右の子が存在すれば rightBoundary(右の子) を呼び出し、存在しなければ rightBoundary(左の子) を呼び出す
   ・再帰から戻った後にノードの値を ret に追加する（これにより右境界が下から上への順序で格納される）
4. leaves()：ノードを受け取る関数を定義する
   ・ノードがNULLの場合は何もせず戻る
   ・ノードが葉であれば、その値を ret に追加する
   ・左右の子に対して再帰的に leaves() を呼び出す
5. メイン処理では以下を実行する
   ・ret をクリアする
   ・根がNULLであれば ret を返す
   ・根の値を ret に追加する
   ・leftBoundary(根の左の子) を呼び出す
   ・leaves(根の左の子) と leaves(根の右の子) を呼び出す
   ・rightBoundary(根の右の子) を呼び出す
   ・ret を返す

C++での実装例

それでは、実際のC++コードを見ていきましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
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:
    vector<int> ret;
    void leftBoundary(TreeNode* node){
        if (!node || node->val == 0 || (!node->left && !node->right))
            return;
        ret.push_back(node->val);
        if (node->left && node->left->val != 0)
            leftBoundary(node->left);
        else
            leftBoundary(node->right);
    }
    void rightBoundary(TreeNode* node){
        if (!node || node->val == 0 || (!node->left && !node->right))
            return;
        if (node->right && node->right->val != 0) {
            rightBoundary(node->right);
        }
        else {
            rightBoundary(node->left);
        }
        ret.push_back(node->val);
    }
    void leaves(TreeNode* node){
        if (!node || node->val == 0)
            return;
        if (!node->left && !node->right) {
            ret.push_back(node->val);
        }
        leaves(node->left);
        leaves(node->right);
    }
    vector<int> boundaryOfBinaryTree(TreeNode* root){
        ret.clear();
        if (!root)
            return ret;
        ret.push_back(root->val);
        leftBoundary(root->left);
        leaves(root->left);
        leaves(root->right);
        rightBoundary(root->right);
        return ret;
    }
};
main(){
    Solution ob;
    vector<int> v = {1,2,3,4,5,6,NULL,NULL,NULL,7,8,9,10};
    TreeNode *root = make_tree(v);
    print_vector(ob.boundaryOfBinaryTree(root));
}

入力

{1,2,3,4,5,6,NULL,NULL,NULL,7,8,9,10}

出力

[1, 2, 4, 7, 8, 9, 10, 6, 3]

計算量について

各ノードを最大1回ずつ訪問するため、時間計算量は O(n) です。また、再帰呼び出しの深さは木の高さに比例するため、空間計算量は O(h)（h は木の高さ）となります。平衡な二分木であれば O(log n)、線形に偏った木の最悪ケースでは O(n) になります。

なお、サンプルコードでは入力ベクトル中の NULL を値 0 のダミーノードとして扱うため、各関数内で node->val == 0 のチェックを行っています。これはテスト用の補助コード固有の処理であり、アルゴリズム本体の考え方には影響しません。