C++で文字列が二分木のルートから葉へのパスとして有効なシーケンスかどうかを判定する方法

問題概要

二分木が与えられ、ルートから任意の葉ノードへ至る各パスが一つのシーケンスを形成するとします。このとき、与えられた整数配列（文字列）が、その二分木における有効なシーケンスであるかどうかを判定するのが本記事のテーマです。

判定対象の文字列は、整数配列 arr の各要素を連結したものとして得られ、パス上のすべてのノードの値を連結した結果がシーケンスとなります。

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

ここで arr = [0,1,0,1] が与えられた場合、出力は True になります。これは、パス 0 → 1 → 0 → 1（緑色で示された経路）が有効なシーケンスだからです。その他の有効なシーケンスとしては、0 → 1 → 1 → 0 や 0 → 0 → 0 などがあります。

解決のためのアプローチ

この問題は、DFS（深さ優先探索）による再帰処理で効率的に解くことができます。以下の手順に従います。

• solve() 関数を定義します。この関数はノード node、配列 v、そして 0 で初期化されるインデックス idx を引数に取ります。
• node が null の場合は false を返します。
• idx が配列 v のサイズ以上になった場合は false を返します。
• node の値が v[idx] と一致しない場合は false を返します。
• node が子を持たない場合（葉ノードに到達した場合）、idx が v のサイズ - 1 と等しければ true を返します。つまり、配列を最後まで消費した状態でちょうど葉に到達したときのみ、有効なシーケンスとみなされます。
• それ以外の場合は、solve(node の左の子, v, idx + 1) と solve(node の右の子, v, idx + 1) を呼び出し、どちらか一方でも true を返せば true を返します。
• メインメソッドからは、solve(root, arr) の結果をそのまま返します。

アルゴリズムのポイント

このアルゴリズムで重要なのは、「配列をすべて使い切ったタイミングで、ちょうど葉ノードに到達していること」を厳密にチェックする点です。パスの途中で配列が尽きてしまったり、逆に葉に達する前に配列を使い切ってしまったりした場合は、いずれも無効なシーケンスとして扱われます。

C++での実装例

理解を深めるために、以下の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;
    }
};
class Solution {
public:
    bool solve(TreeNode* node, vector <int>& v, int idx = 0){
        if(!node) return false;
        if(idx >= v.size()) return false;
        if(node->val != v[idx]) return false;
        if(!node->left && !node->right){
            return idx == v.size() - 1;
        }
        return solve(node->left, v, idx + 1) || solve(node->right, v, idx + 1);
    }
    bool isValidSequence(TreeNode* root, vector<int>& arr) {
        return solve(root, arr);
    }
};
main(){
    TreeNode *root = new TreeNode(0);
    root->left = new TreeNode(1); root->right = new TreeNode(0);
    root->left->left = new TreeNode(0); root->left->right = new
    TreeNode(1);
    root->right->left = new TreeNode(0);
    root->left->left->right = new TreeNode(1);
    root->left->right->left = new TreeNode(0); root->left->right->right = new TreeNode(0);
    Solution ob;
    vector<int> v = {0,1,0,1};
    cout << (ob.isValidSequence(root, v));
}

入力

TreeNode *root = new TreeNode(0);
root->left = new TreeNode(1); root->right = new TreeNode(0);
root->left->left = new TreeNode(0); root->left->right = new
TreeNode(1);
root->right->left = new TreeNode(0);
root->left->left->right = new TreeNode(1);
root->left->right->left = new TreeNode(0); root->left->right->right = new TreeNode(0);

出力

1

出力は 1（true）となり、配列 [0,1,0,1] がこの二分木における有効なシーケンスであることが確認できました。

計算量について

時間計算量は O(N) です（N は木のノード数）。各ノードは最大一度ずつ訪問され、訪問のたびに配列との照合が行われます。ただし、配列の接頭辞と一致しない部分木は早期に切り捨てられるため、実際の探索範囲はさらに狭まります。空間計算量は再帰スタックの深さに依存し、最悪の場合で木の高さ H に比例する O(H) となります。