C++で二分木の最長連続増加パスの長さを求める方法

二分木が与えられたとき、値が連続して増加するノードから構成される最長のパスの長さを計算することを考えます。ここで、すべてのノードは単体で長さ1のパスとして扱われるものとします。

例えば、次のような二分木が入力として与えられた場合を考えてみましょう。

この場合、(11, 12, 13) が最も長い連続増加パスとなるため、出力は 3 になります。

解法のアプローチ

この問題を解くために、以下の手順に従います。

• 再帰関数 solve() を定義します。引数として root（現在のノード）、prev_data（前のノードの値）、prev_length（現在のパスの長さ）を受け取ります。
• root が NULL の場合：
  • これ以上探索できないため、prev_length をそのまま返します。
• 現在のノードの値を cur_data とします。
• もし cur_data == prev_data + 1（値が連続している）ならば：
  • 左部分木と右部分木それぞれに対して solve() を呼び出し、パスの長さを1増やした結果のうち大きい方を返します。
• 連続していない場合は、新しいパスを開始します。newPathLen を左部分木と右部分木に対して長さ1から再び探索した結果の最大値とします。
• 最後に、prev_length と newPathLen のうち大きい方を返します。

メイン関数での処理

• root が NULL の場合は 0 を返します。
• それ以外の場合は solve(root, rootの値 - 1, 0) を返します。初期値を「rootの値 - 1」にすることで、ルート自身から必ず連続判定が成立するようにしています。

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;
    }
};
int solve(TreeNode *root, int prev_data, int prev_length){
   if (!root)
      return prev_length;
   int cur_data = root->val;
   if (cur_data == prev_data+1){
      return max(solve(root->left, cur_data, prev_length+1), solve(root->right, cur_data, prev_length+1));
   }
   int newPathLen = max(solve(root->left, cur_data, 1), solve(root->right, cur_data, 1));
   return max(prev_length, newPathLen);
}
int maxLen(TreeNode *root){
   if (root == NULL)
      return 0;
   return solve(root, root->val-1, 0);
}
int main(){
   TreeNode *root = new TreeNode(10);
   root->left = new TreeNode(11);
   root->right = new TreeNode(9);
   root->left->left = new TreeNode(13);
   root->left->right = new TreeNode(12);
   root->right->left = new TreeNode(13);
   root->right->right = new TreeNode(8);
   cout << maxLen(root);
   return 0;
}

入力

TreeNode *root = new TreeNode(10);
root->left = new TreeNode(11);
root->right = new TreeNode(9);
root->left->left = new TreeNode(13);
root->left->right = new TreeNode(12);
root->right->left = new TreeNode(13);
root->right->right = new TreeNode(8);

出力

3

まとめ

このアルゴリズムは、各ノードを一度だけ訪問するため、時間計算量は O(n)、再帰呼び出しによる空間計算量は木の高さに依存し、最悪の場合 O(n) となります。親子間で値が1ずつ増加するパスを再帰的に追跡することで、効率的に最長の連続増加パスを求めることができます。