数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学检查字符串是否为 C++ 中二叉树中从根到叶路径的有效序列
假设我们有一个二叉树，其中从根到任何叶子的每条路径都形成一个有效的序列，我们必须检查给定的字符串是否为此二叉树中的有效序列。
我们将从整数数组 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
如果节点的值不等于 v[idx]，则：
返回 false
如果节点没有子节点，则：
当 idx == v 的大小，返回 true
返回 solve(节点的左子节点, v, idx + 1)
从主方法执行以下操作：
返回 solve(根节点, 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
更新于：2020-11-17
149 次查看
广告