루트에서 잎으로 가는 각 경로가 유효한 시퀀스를 형성하는 이진 트리가 있다고 가정하면 주어진 문자열이 이러한 이진 트리에서 유효한 시퀀스인지 확인해야 합니다.
정수 배열 arr의 연결에서 주어진 문자열을 얻고 경로를 따라 노드의 모든 값을 연결하면 시퀀스가 생성됩니다.
다음과 같은 이진 트리가 있다고 가정합니다.
따라서 arr =[0,1,0,1]이면 경로 0 -> 1 -> 0 -> 1이 유효한 시퀀스(녹색)이므로 출력은 True가 됩니다. 다른 유효한 시퀀스는 다음과 같습니다. 0 -> 1 -> 1 -> 0 , 0 -> 0 -> 0
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
solve() 함수를 정의하면 노드, 배열 v, idx가 0으로 초기화됩니다.
-
노드가 null이면 -
-
거짓을 반환
-
-
idx>=v의 크기인 경우 -
-
거짓을 반환
-
-
노드의 val이 v[idx]와 같지 않으면 -
-
거짓을 반환
-
-
노드에 자식이 없으면 -
-
idx ==v의 크기
인 경우 true를 반환합니다.
-
-
해결 반환(노드 왼쪽, v, idx + 1)
-
기본 방법에서 다음을 수행하십시오 -
-
해결(루트, 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