資料結構
網路
關係資料庫管理系統 (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 次檢視
廣告