สมมติว่าเรามีไบนารีทรีที่แต่ละเส้นทางเดินทางจากรูทไปยังลีฟในรูปแบบลำดับที่ถูกต้อง เราต้องตรวจสอบว่าสตริงที่กำหนดเป็นลำดับที่ถูกต้องในไบนารีทรีดังกล่าวหรือไม่
เราจะได้สตริงที่กำหนดจากการต่ออาร์เรย์ของจำนวนเต็ม arr และการต่อกันของค่าทั้งหมดของโหนดตามพาธส่งผลให้มีลำดับ
สมมติว่าเรามีต้นไม้ไบนารีเช่น
ดังนั้น ถ้า arr =[0,1,0,1] ผลลัพธ์จะเป็น True เนื่องจากเส้นทาง 0 -> 1 -> 0 -> 1 เป็นลำดับที่ถูกต้อง (สีเขียว) ลำดับที่ถูกต้องอื่น ๆ จะเป็น :0 -> 1 -> 1 -> 0 , 0 -> 0 -> 0
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดฟังก์ชัน Solve() ซึ่งจะใช้โหนด, อาร์เรย์ v, idx เริ่มต้นด้วย 0
-
ถ้าโหนดเป็นโมฆะ −
-
คืนค่าเท็จ
-
-
ถ้า idx>=ขนาดของ v แล้ว −
-
คืนค่าเท็จ
-
-
ถ้า val ของโหนดไม่เท่ากับ v[idx] ดังนั้น −
-
คืนค่าเท็จ
-
-
ถ้าโหนดไม่มีลูก −
-
คืนค่าจริงเมื่อ idx ==ขนาดของ v
-
-
คืนค่าแก้ (ด้านซ้ายของโหนด, v, idx + 1)
-
จากวิธีหลักให้ทำดังต่อไปนี้ -
-
ส่งคืนการแก้ (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
