C++の二分木の最大連続増加パス長

二分木があるとしましょう。昇順で連​​続する値を持つノードで構成される最長のパスの長さを計算する必要があります。すべてのノードは長さ1のパスとして扱われます。

したがって、入力が次のような場合

（11、12、13）が最大連続パスであるため、出力は3になります。

これを解決するには、次の手順に従います-

• 関数solve（）を定義します。これにより、root、prev_data、prev_length、
が取得されます。
• ルートがゼロ以外の場合、-
  • prev_lengthを返す
• cur_data：=ルートの値
• cur_dataがprev_data+1と同じ場合、-
  • solve（ルートの左側、cur_data、prev_length + 1）とsolve（ルートの右側、cur_data、prev_length + 1）の最大値を返します
• newPathLen：=solve（ルートの左側、cur_data、1）とsolve（ルートの右側、cur_data、1）の最大値
• prev_lengthとnewPathLenの最大値を返します
• メインの方法から次のようにします-
• rootがNULLと同じ場合、-
  • 0を返す
• returnsolve（ルート、ルートの値-1、0）

例（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