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

二分木があるとしましょう。連続する最長のシーケンスパスの長さを見つけることができるかどうかを確認する必要があります。パスが、親子接続に沿ったツリー内の開始ノードから任意のノードまでのノードのシーケンスを参照している場合。最長の連続パスは、親から子をたどる必要がありますが、逆にする必要はありません。

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

最長の連続シーケンスパスは3-4-5であるため、出力は3になります。したがって、3を返します。

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

• 関数solveUtil（）を定義します。これにより、ノード、prev、lenが1で初期化されます

  。

• ノードがnullの場合、-

  • 戻る

• prev + 1がノードのvalと同じである場合、-

  • （lenを1増やします）

  • ans：=ansとlenの最大値

  • resolveUtil（ノードの左側、ノードの値、len）

  • solveUtil（ノードの権利、ノードのval、len）

• それ以外の場合

  • solveUtil（ノードの左側、ノードの値、1）

  • solveUtil（ノードの権利、ノードの値、1）

• 関数solve（）を定義します。これにはAが必要です

• ans：=1

• resolveUtil（A、-infinity）

• ansを返す

• メインの方法から、次のようにします-

• ルートがnullの場合、-

  • 0を返す

• リターンソルブ（ルート）

例

理解を深めるために、次の実装を見てみましょう-

#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));
}

入力

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