文字列がC++のバイナリツリーのルートからリーフパスまでの有効なシーケンスであるかどうかを確認します

ルートから任意のリーフに向かう各パスが有効なシーケンスを形成するバイナリツリーがあるとすると、特定の文字列がそのようなバイナリツリーで有効なシーケンスであるかどうかを確認する必要があります。

整数の配列arrの連結から指定された文字列を取得し、パスに沿ったノードのすべての値を連結すると、シーケンスが生成されます

のような二分木があるとします。

したがって、arr =[0,1,0,1]の場合、パス0-> 1-> 0-> 1は有効なシーケンス（緑色）であるため、出力はTrueになります。他の有効なシーケンスは次のようになります：0-> 1-> 1-> 0、0-> 0-> 0

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

• 関数solve（）を定義します。これにより、ノード、配列vが取得され、idxが0で初期化します。

• ノードがnullの場合、-

  • falseを返す

• idx> =vのサイズの場合、-

  • falseを返す

• ノードのvalがv[idx]と等しくない場合、-

  • falseを返す

• ノードに子がない場合、-

  • idx==vのサイズ

    の場合はtrueを返します

• リターンソルブ（ノードの左側、v、idx + 1）

• メインメソッドから次のようにします-

• リターンsolve（root、arr）

例

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

#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:
   bool solve(TreeNode* node, vector <int>& v, int idx = 0){
      if(!node) return false;
      if(idx >= v.size()) return false;
      if(node->val != v[idx]) return false;
      if(!node->left && !node->right){
         return idx == v.size() - 1;
      }
      return solve(node->left, v, idx + 1) || solve(node->right, v, idx + 1);
   }
   bool isValidSequence(TreeNode* root, vector<int>& arr) {
      return solve(root, arr);
   }
};
main(){
   TreeNode *root = new TreeNode(0);
   root->left = new TreeNode(1); root->right = new TreeNode(0);
   root->left->left = new TreeNode(0); root->left->right = new
   TreeNode(1);
   root->right->left = new TreeNode(0);
   root->left->left->right = new TreeNode(1);
   root->left->right->left = new TreeNode(0); root->left->right->right = new TreeNode(0);
   Solution ob;
   vector<int> v = {0,1,0,1};
   cout << (ob.isValidSequence(root, v));
}

入力

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

出力

1