C++で解く二分木の擬似回文パス問題 ― DFSによる数え方

問題の概要

ノードの値が 1 から 9 の数字である二分木を考えます。根ノードから葉ノードへ向かうあるパスについて、パスに含まれるノード値を並べ替えた結果の少なくとも1つが回文になるとき、そのパスを「擬似回文パス（pseudo-palindromic path）」と呼びます。この問題では、根から葉への擬似回文パスが全部で何本あるかを求めます。

具体例

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

このとき出力は 2 になります。根ノードから葉ノードへの経路は3本存在します。赤のパスは [2,3,3]、緑のパスは [2,1,1]、そして残りのパスは [2,3,1] です。このうち擬似回文パスになっているのは赤と緑の2本だけです。赤のパス [2,3,3] は [3,2,3] と並べ替えられ、緑のパス [2,1,1] は [1,2,1] と並べ替えられるため、どちらも回文を作れます。一方、[2,3,1] はどのように並べ替えても回文にできないため、対象外となります。

解法のポイント：回文の判定条件

ある数列を並べ替えて回文にできるための必要十分条件は、「奇数回出現する値が高々1種類であること」です。この性質を利用すれば、パス上の各値の出現回数を数えておき、葉に到達した時点で奇数回出現する値の種類が 0 または 1 かどうかを確認するだけで判定できます。

アルゴリズムの手順

1. 関数 ok() を定義します。引数は出現回数を格納した配列 v です。
2. odd := 0 と初期化します。
3. v の各要素 it に対して、odd := odd + (it AND 1) を計算します（奇数の個数を数える）。
4. odd が 0 または 1 であれば true を返し、それ以外は false を返します。
5. 関数 dfs() を定義します。引数はノード node と配列 v です。
6. node が null の場合は何もせずに戻ります。
7. v[node の値] を 1 増やします。
8. node の左の子と右の子がどちらも null（葉ノード）の場合：
   • ok(v) が true なら、答え ret を 1 増やします。
   • v[node の値] を 1 減らして（バックトラックして）戻ります。
9. dfs(左の子, v) と dfs(右の子, v) を再帰的に呼び出します。
10. 最後に v[node の値] を 1 減らして戻ります。

メインの処理では、ret := 0 と初期化し、サイズ 10 のカウント用配列 cnt を用意して dfs(root, cnt) を呼び出し、最後に ret を返します。

計算量

各ノードを一度だけ訪問するため、時間計算量は O(N)（N はノード数）、必要な追加メモリは再帰の深さとカウント配列分の O(H)（H は木の高さ）となります。

実装例

以下の 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 ret;
    bool ok(vector <int>& v){
        int odd = 0;
        for (auto& it : v) {
            odd += it & 1;
        }
        return odd == 0 || odd == 1;
    }
    void dfs(TreeNode* node, vector <int>& v){
        if (!node)
            return;
        v[node->val]++;
        if (!node->left && !node->right) {
            if (ok(v))
                ret++;
            v[node->val]--;
            return;
        }
        dfs(node->left, v);
        dfs(node->right, v);
        v[node->val]--;
    }
    int pseudoPalindromicPaths (TreeNode* root) {
        ret = 0;
        vector<int> cnt(10);
        dfs(root, cnt);
        return ret;
    }
};
main(){
    Solution ob;
    vector<int> v = {2,3,1,3,1,NULL,1};
    TreeNode *root = make_tree(v);
    cout << (ob.pseudoPalindromicPaths(root));
}

入力

{2,3,1,3,1,NULL,1}

出力

2

まとめ

この問題は、DFS で根から葉へのすべての経路を探索しながら出現回数を管理し、葉に到達した時点で「奇数回出現する値が 1 種類以下」という回文の成立条件をチェックすることで効率的に解けます。バックトラックでカウントを正しく戻すことが実装上のポイントです。