Khi cần kiểm tra sự tồn tại của một đường đi từ nút gốc đến nút lá sao cho tổng giá trị các nút trên đường đi đó bằng một số cho trước (Path Sum), chiến lược xử lý tối ưu trên Binary Tree là gì?

Question

Accepted Answer

Bài toán Path Sum kiểm tra xem cây có chứa đường đi từ gốc đến lá mà tổng giá trị các nút khớp với giá trị mục tiêu (Target Sum) hay không. Đây là bài toán kiểm tra kỹ năng áp dụng tư duy đệ quy vét cạn có kiểm soát.
Bản chất kỹ thuật
Chúng ta có thể giải quyết bài toán này bằng cách trừ dần giá trị của nút hiện tại ra khỏi targetSum mỗi khi đi xuống các nút con. Khi duyệt đến một nút lá (không có cả con trái lẫn con phải), chúng ta chỉ cần kiểm tra xem giá trị targetSum còn lại có bằng đúng giá trị của nút lá đó hay không.
Giải pháp mã nguồn minh họa (Java)
public class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }

// Kiểm tra xem nút hiện tại có phải là nút lá hay không
        if (root.left == null && root.right == null) {
            return targetSum == root.val;
        }

int remainingSum = targetSum - root.val;

// Đệ quy kiểm tra nhánh trái hoặc nhánh phải
        return hasPathSum(root.left, remainingSum) || hasPathSum(root.right, remainingSum);
    }
}
Kinh nghiệm thực chiến Enterprise

Độ phức tạp thời gian: O(N) trong trường hợp xấu nhất phải duyệt qua tất cả các nút trên cây.
Độ phức tạp không gian: O(H) với H là chiều cao của cây do Stack lưu trữ các lời gọi đệ quy.
Lời khuyên tối ưu: Tránh việc tính toán lại tổng giá trị từ đầu ở mỗi nút lá. Việc trừ dần giá trị vào biến targetSum giúp giảm thiểu các phép tính thừa và tối ưu hóa hiệu năng thực thi của hàm.

Khi cần kiểm tra sự tồn tại của một đường đi từ nút gốc đến nút lá sao cho tổng giá trị các nút trên đường đi đó bằng một số cho trước (Path Sum), chiến lược xử lý tối ưu trên Binary Tree là gì?

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 binary tree liên quan cùng chủ đề