C++で解く二分木の最長連続シーケンス II

この記事では、二分木が与えられたときに、その木の中で最長連続パス(Longest Consecutive Path)の長さを求めるアルゴリズムをC++で実装する方法を解説します。

問題の概要

二分木において、以下の条件を満たすパスのうち最も長いものの長さを見つけます。

• パスは増加方向でも減少方向でも構いません。つまり [1, 2, 3, 4] と [4, 3, 2, 1] はどちらも有効なパスですが、[1, 2, 4, 3] のように順序が混在したものは無効です。
• パスは子 → 親 → 子の順序であってもよく、必ずしも親から子への一方向である必要はありません。

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

この場合、最長の連続パスは [1, 2, 3] または [3, 2, 1] となるため、出力は 3 になります。

解法のアプローチ

この問題は、各ノードを起点とした「増加連続パスの長さ」と「減少連続パスの長さ」を再帰的に計算することで解けます。手順は以下の通りです。

アルゴリズムの手順

1. ノードを引数にとる関数 solveUtil() を定義します。
2. ノードが null の場合は {0, 0} を返します。
3. 左部分木・右部分木それぞれに対して solveUtil() を再帰呼び出しします。
4. ペア temp = {1, 1} を用意します。first は増加連続の長さ、second は減少連続の長さを表します。
5. 左の子が存在し、その値が現在のノードの値 + 1 と等しい場合:
   • temp.first を temp.first と 1 + left.first の最大値で更新
   • ans を ans と temp.first の最大値で更新
6. 右の子が存在し、その値が現在のノードの値 + 1 と等しい場合も同様に処理します。
7. 左の子が存在し、その値が現在のノードの値 − 1 と等しい場合:
   • temp.second を temp.second と 1 + left.second の最大値で更新
   • ans を ans と temp.second の最大値で更新
8. 右の子についても同様に処理します。
9. 子→親→子のパスを考慮するため、ans を temp.first + temp.second − 1(自分自身を重複カウントしないため −1)とも比較して更新します。
10. temp を返します。

メインメソッドでの処理

1. ans を 0 で初期化します。
2. solveUtil(root) を呼び出します。
3. ans を返します。

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:
    int ans = 0;
    pair<int, int> solveUtil(TreeNode* node){
        if (!node) {
            return { 0, 0 };
        }
        pair<int, int> left = solveUtil(node->left);
        pair<int, int> right = solveUtil(node->right);
        pair<int, int> temp = { 1, 1 };
        if (node->left && node->left->val == node->val + 1) {
            temp.first = max(temp.first, 1 + left.first);
            ans = max(ans, temp.first);
        }
        if (node->right && node->right->val == node->val + 1) {
            temp.first = max(temp.first, 1 + right.first);
            ans = max(ans, temp.first);
        }
        if (node->left && node->left->val == node->val - 1) {
            temp.second = max(temp.second, 1 + left.second);
            ans = max(ans, temp.second);
        }
        if (node->right && node->right->val == node->val - 1) {
            temp.second = max(temp.second, 1 + right.second);
            ans = max(ans, temp.second);
        }
        ans = max({ ans, temp.first + temp.second - 1 });
        return temp;
    }
    int longestConsecutive(TreeNode* root){
        ans = 0;
        solveUtil(root);
        return ans;
    }
};
main(){
    Solution ob;
    TreeNode *root = new TreeNode(2);
    root->left = new TreeNode(1);
    root->right = new TreeNode(3);
    cout << (ob.longestConsecutive(root));
}

入力

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

出力

3

計算量について

このアルゴリズムは各ノードを一度だけ訪問するため、時間計算量は O(N)(N はノード数)、空間計算量は再帰スタックの深さ分となり、最悪の場合(木が偏っているとき)O(N)、バランスの取れた木では O(log N) となります。