使用 C++ 检查二叉树中字符串是否为从根到叶路径的有效序列
c++server side programmingprogramming
假设我们有一个二叉树，其中从根到任何叶的每条路径都形成一个有效序列，我们必须检查给定的字符串是否是这种二叉树中的有效序列。
我们将从整数数组 arr 的串联中获取给定的字符串，并将路径上所有节点的值串联起来得到一个序列
假设我们有一个二叉树。
因此，如果 arr = [0,1,0,1]，则输出将为 True，因为路径0 -> 1 -> 0 -> 1 是有效序列(绿色)。其他有效序列为:0 -> 1 -> 1 -> 0、0 -> 0 -> 0
为了解决这个问题，我们将遵循以下步骤 −
定义一个函数solve()，它将获取节点、数组v、idx并将其初始化为0，
如果节点为空，则 −
返回false
如果idx >= v的大小，则 −
返回false
如果节点的val不等于v[idx]，则 −
返回false
如果节点没有子节点，则−
当 idx == v 的大小时返回 true
返回 resolve(节点左侧, v, idx + 1)
从主方法执行以下操作 −
return 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
