Kiểm tra chuỗi có phải trình tự hợp lệ từ gốc đến lá trong cây nhị phân trong C++

Giới thiệu

Cho cây nhị phân và mảng số nguyên arr. Kiểm tra xem có đường đi từ gốc đến lá nào mà nối các giá trị nút theo thứ tự chính xác bằng arr hay không.

Thuật toán: DFS đệ quy

Duyệt cây từ gốc, so sánh từng nút với arr[idx]:

• Nếu nút null hoặc giá trị không khớp → false.
• Nếu đến lá: trả về idx == arr.size()-1.
• Đệ quy sang trái/phải với idx+1.

Cài đặt 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;
        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() {
    // Xây cây ví dụ
    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> arr = {0,1,0,1};
    cout << ob.isValidSequence(root, arr); // Output: 1 (true)
    return 0;
}

Phân tích

• Thời gian: O(N) – mỗi nút được thăm tối đa 1 lần.
• Không gian: O(H) – stack đệ quy, H = chiều cao cây.

LeetCode 1430 "Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree".