Làm thế nào để tìm kiếm giá trị theo chiều sâu sử dụng Stack thủ công thay vì đệ quy khi duyệt cây (Path Sum check)?

Question

Accepted Answer

Bản chất vấn đề
Nhiều hệ thống production cấm sử dụng đệ quy quá sâu để tránh lỗi Stack Overflow trên production server. Do đó, việc biết cách triển khai thuật toán Duyệt theo chiều sâu (DFS) sử dụng Stack thủ công kết hợp lưu trữ trạng thái tổng đường đi là kỹ năng bắt buộc đối với lập trình viên hướng tới cấp độ chuyên nghiệp.
Hướng giải quyết chi tiết
Bài toán kiểm tra xem có tồn tại đường đi từ gốc đến lá sao cho tổng các giá trị trên đường đi bằng một số cho trước (targetSum) hay không:

Sử dụng một Stack lưu trữ các cặp giá trị: (nút hiện tại, tổng còn lại cần tìm).
Đưa nút gốc và targetSum - root.val vào Stack.
Lặp lại cho đến khi Stack rỗng:
Lấy ra nút và giá trị tổng còn lại.
Kiểm tra nếu đó là nút lá và tổng còn lại bằng 0 thì trả về true.
Nếu có con phải, đưa con phải và giá trị tổng còn lại trừ đi giá trị con phải vào Stack.
Nếu có con trái, đưa con trái và giá trị tổng còn lại trừ đi giá trị con trái vào Stack.

Ví dụ mã nguồn minh họa (TypeScript)
class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val===undefined ? 0 : val)
        this.left = (left===undefined ? null : left)
        this.right = (right===undefined ? null : right)
    }
}

function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
    if (!root) return false;

const stack: [TreeNode, number][] = [[root, targetSum - root.val]];

while (stack.length > 0) {
        const [node, remainingSum] = stack.pop()!;

// Kiểm tra nếu là nút lá và thỏa mãn điều kiện
        if (!node.left && !node.right && remainingSum === 0) {
            return true;
        }

if (node.right) {
            stack.push([node.right, remainingSum - node.right.val]);
        }
        if (node.left) {
            stack.push([node.left, remainingSum - node.left.val]);
        }
    }

return false;
}
Độ phức tạp

Độ phức tạp thời gian: O(N) trong trường hợp xấu nhất phải duyệt qua toàn bộ các nút.
Độ phức tạp không gian: O(H) lưu trữ các phần tử trên Stack thủ công.

Kinh nghiệm thực chiến
Kỹ thuật khử đệ quy bằng Stack tường minh giúp kiểm soát tốt bộ nhớ Heap thay vì phụ thuộc vào Call Stack của ngôn ngữ lập trình, điều này cực kỳ hữu ích khi xây dựng các bộ phân tích cú pháp (Parser) hoặc xử lý cây cú pháp trừu tượng (AST) trong các trình biên dịch hoặc công cụ build.

Làm thế nào để tìm kiếm giá trị theo chiều sâu sử dụng Stack thủ công thay vì đệ quy khi duyệt cây (Path Sum check)?

Bản chất vấn đề

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi trees liên quan cùng chủ đề