【C++】二分木における最長連続シーケンス経路の求め方を解説

問題の概要

二分木が与えられたとき、最長の連続シーケンス経路の長さを求める問題を考えます。ここで「経路」とは、ある開始ノードから親子のつながり(親から子へのエッジ)に沿って、木の中の任意のノードまでをたどるノードの列を指します。最長の連続経路は必ず親から子の方向へ進む必要があり、逆方向(子から親)へさかのぼることは認められません。

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

この場合、最長の連続シーケンス経路は 3 → 4 → 5 となるため、出力は 3 になります。

アルゴリズムのアプローチ

この問題は、木を深さ優先探索(DFS)でたどりながら、連続する値の並びを追跡することで解くことができます。具体的な手順は以下の通りです。

1. 関数 solveUtil() を定義します。引数は node(現在のノード)、prev(親ノードの値)、len(現在の連続長、初期値は 1)です。
2. node が null の場合は何もせずに return します。
3. prev + 1 が node の値と等しい場合(連続している場合):
   • len を 1 増やします。
   • ans を ans と len の最大値で更新します。
   • solveUtil(node の左の子、node の値、len) を呼び出します。
   • solveUtil(node の右の子、node の値、len) を呼び出します。
4. それ以外の場合(連続が途切れた場合):
   • solveUtil(node の左の子、node の値、1) を呼び出します。
   • solveUtil(node の右の子、node の値、1) を呼び出します。
5. 関数 solve() を定義します。引数は A(ルートノード)です。
6. ans を 1 で初期化します。
7. solveUtil(A, -無限大) を呼び出します。
8. ans を返します。
9. メインの処理では以下を行います。
   • root が null の場合は 0 を返します。
   • それ以外は solve(root) の結果を返します。

実装例

それでは、以下の 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 ans;
   void solveUtil(TreeNode* node, int prev, int len = 1){
      if (!node)
         return;
      if (prev + 1 == node->val) {
         len++;
         ans = max(ans, len);
         solveUtil(node->left, node->val, len);
         solveUtil(node->right, node->val, len);
      }
      else {
         solveUtil(node->left, node->val, 1);
         solveUtil(node->right, node->val, 1);
      }
   }
   int solve(TreeNode* A){
      ans = 1;
      solveUtil(A, INT_MIN);
      return ans;
   }
   int longestConsecutive(TreeNode* root){
      if (!root)
         return 0;
      return solve(root);
   }
};
main(){
   Solution ob;
   TreeNode *root = new TreeNode(1);
   root->right = new TreeNode(3);
   root->right->left = new TreeNode(2);
   root->right->right = new TreeNode(4);
   root->right->right->right = new TreeNode(5);
   cout << (ob.longestConsecutive(root));
}

計算量の目安

このアルゴリズムの計算量は以下の通りです。

• 時間計算量:O(N) ― 各ノードを一度だけ訪問するため、ノード数を N とすると線形時間で処理できます。
• 空間計算量:O(H) ― 再帰呼び出しのスタックの深さは木の高さ H に依存します。木が偏っている場合は O(N)、バランスが取れている場合は O(log N) となります。

入力

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

出力

3

まとめ

二分木の最長連続シーケンス経路の問題は、DFS を使って親から子へ値が 1 ずつ増えているかどうかを追跡するだけで解決できます。連続が途切れた時点でカウントを 1 にリセットし、最大値を随時更新していくというシンプルな発想がポイントです。木構造の探索問題に慣れるための良い練習題材なので、ぜひ自分でも実装してみてください。