Check Valid Sequence in Binary Tree – ตรวจสอบลำดับถูกต้องใน C++

ปัญหา: Check If a String Is a Valid Sequence from Root to Leaves Path

กำหนด Binary Tree และอาร์เรย์ arr ตรวจสอบว่า arr เป็น valid sequence หรือไม่ โดย valid sequence = ลำดับค่าจากรากถึงใบ (root-to-leaf path) ที่ตรงกับ arr ทุกตัว

ตัวอย่าง

Tree:

      0
     / \
    1   0
   / \ /
  0  1 0
   \ / \
   1 0 0

arr = [0,1,0,1] → Path: 0→1→0→1 (สีเขียว) → true

แนวทางแก้ปัญหา: DFS Recursive

ขั้นตอน

1. ฟังก์ชัน dfs(node, arr, idx) – idx = ตำแหน่งปัจจุบันใน arr
2. Base cases:
   • node == null → false
   • idx >= arr.size() → false
   • node->val != arr[idx] → false
3. ถ้าโหนดเป็นใบ (!left && !right) → คืน idx == arr.size()-1 (ต้องจบพอดี)
4. Recursive: dfs(left, arr, idx+1) || dfs(right, arr, idx+1)

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    bool isValidSequence(TreeNode* root, vector<int>& arr) {
        return dfs(root, arr, 0);
    }

    bool dfs(TreeNode* node, vector<int>& arr, int idx) {
        if (!node) return false;
        if (idx >= arr.size()) return false;
        if (node->val != arr[idx]) return false;

        // leaf node
        if (!node->left && !node->right)
            return idx == arr.size() - 1;

        return dfs(node->left, arr, idx + 1) || dfs(node->right, arr, idx + 1);
    }
};

int main() {
    // Build tree from example
    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) ? "true" : "false"); // true
    return 0;
}

ความซับซ้อน

• เวลา: O(N) – เยี่ยมแต่ละโหนดสูงสุด 1 ครั้ง (prune ได้เร็วเมื่อค่าไม่ตรง)
• พื้นที่: O(H) – recursion stack, H = ความสูงต้นไม้

ข้อสังเกต

• LeetCode 1430
• สำคัญ: ต้องจบที่ ใบ (leaf) พอดี – ไม่ใช่แค่ path เริ่มต้นตรง
• Early termination: คืน false ทันทีเมื่อค่าไม่ตรงหรือ idx เกิน
• Iterative DFS ด้วย stack ก็ได้ แต่ recursive เขียนสั้นกว่า