Path Sum

Q: Độ phức tạp thời gian của Path Sum là bao nhiêu?

O(n) : mỗi nút được duyệt nhiều nhất một lần và quá trình tìm kiếm có thể dừng lại ở lá đầu tiên khớp. Không gian bổ sung là O(h) cho đường đi đang được khám phá, dưới dạng các khung gọi hàm hoặc các phần tử trên ngăn xếp của riêng bạn.

DễDuyệt cây

+10

Bạn nhận được một cây nhị phân được lưu trong mảng tree theo thứ tự từng tầng và một số targetSum. Gốc nằm ở chỉ số 0, các con của nút ở chỉ số i nằm tại 2*i+1 (bên trái) và 2*i+2 (bên phải), -1 đánh dấu một vị trí trống và mảng có thể kết thúc bằng các phần tử -1 thừa. Trả về true nếu có đường đi từ gốc xuống một nút lá sao cho tổng các giá trị trên đường đi bằng targetSum, nếu không thì trả về false. Nút lá là nút có cả hai vị trí con đều trống.

Hàm

hasPathSum(tree: integer-array, targetSum: integer) → boolean

treeinteger-array: cây nhị phân theo thứ tự từng tầng, dùng -1 cho vị trí trống
targetSuminteger: tổng mà một đường đi từ gốc đến lá phải đạt được
Trả vềboolean: true nếu có đường đi nào từ gốc đến lá có tổng bằng targetSum, false nếu không

Ràng buộc

1 ≤ tree.length ≤ 32767
Mỗi tree[i] là -1 hoặc một giá trị thỏa mãn 0 ≤ tree[i] ≤ 1000.
tree[0] không bao giờ là -1, vì vậy cây có ít nhất một nút.
Mảng có thể kết thúc bằng các phần tử -1 bổ sung sau nút cuối cùng.
Cả hai nút con của một vị trí trống cũng đều trống, và độ sâu tối đa là 14.
0 ≤ targetSum ≤ 15000

Ví dụ

Đầu vào: tree = [3, 9, 6, -1, 2, 1, 7]targetSum = 14
Đầu ra: true
Giải thích: Đường đi 3, 9, 2 (các chỉ số 0, 1, 4) có tổng bằng 14, và 2 ở chỉ số 4 là một nút lá.

Đầu vào: tree = [3, 9, 6, -1, 2, 1, 7]targetSum = 12
Đầu ra: false
Giải thích: 3 + 9 = 12, nhưng 9 có một nút con, nên không có đường đi nào kết thúc ở đó. Tổng các giá trị trên ba đường đi từ nút gốc đến nút lá lần lượt là 14, 10 và 16, không có đường nào có tổng bằng 12.

Đầu vào: tree = [4, -1, -1]targetSum = 4
Đầu ra: true
Giải thích: Cả hai vị trí con của nút gốc đều trống, nên nút gốc tự nó là một nút lá. Đường đi chỉ chứa 4 có tổng bằng 4.

Câu hỏi mở rộng

Bạn có thể đếm số đường đi có tổng bằng targetSum nếu đường đi có thể bắt đầu từ bất kỳ nút nào và kết thúc ở bất kỳ nút nào bên dưới nó không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Chỉ tính các đường đi hoàn chỉnh, từ nút gốc xuống nút lá. Tổng đang tính có thể bằng targetSum tại một nút vẫn còn nút con, nhưng trường hợp đó không được tính. Vì vậy, hãy truyền tổng của đường đi xuống từng nút dưới dạng tham số hoặc lưu trên ngăn xếp, rồi chỉ so sánh với mục tiêu tại các nút lá.

Đệ quy trên tổng còn lại

Ý tưởng

Một đường đi có tổng bằng targetSum bắt đầu bằng giá trị của nút gốc, nên phần còn lại của đường đi, bắt đầu từ một trong các nút con của nút gốc, phải có tổng bằng targetSum trừ đi giá trị đó. Đó cũng là câu hỏi tương tự trên một cây nhỏ hơn. Trừ giá trị của mỗi nút khi đi xuống; tại nút lá, đường đi kết thúc, nên câu trả lời là liệu còn lại gì hay không.

Trong ví dụ đầu tiên, nút gốc để lại 14 - 3 = 11, nút 9 để lại 2 và nút lá 2 để lại 0. Trong ví dụ thứ hai, nút 9 đã để lại 0, nhưng nó có nút con nên quá trình tìm kiếm tiếp tục. Mỗi nút được duyệt một lần, thời gian O(n), và ngăn xếp lời gọi chứa một khung cho mỗi cấp, nhiều nhất là 15.

Thuật toán

Viết walk(i, remaining) và trừ tree[i] khỏi remaining.
Nếu cả hai vị trí con của i đều trống (chỉ số vượt quá cuối mảng hoặc là -1), hãy trả về kết quả cho biết remaining có bằng 0 hay không.
Nếu không, hãy trả về true nếu lời gọi walk trên nút con trái tồn tại hoặc nút con phải tồn tại trả về true.
Trả về walk(0, targetSum).

def hasPathSum(tree, targetSum):
    n = len(tree)

    def walk(i, remaining):
        # remaining is what the path still needs once it reaches node i.
        remaining -= tree[i]
        left, right = 2 * i + 1, 2 * i + 2
        has_left = left < n and tree[left] != -1
        has_right = right < n and tree[right] != -1
        if not has_left and not has_right:
            return remaining == 0  # a leaf: the path ends here
        return (has_left and walk(left, remaining)) or (has_right and walk(right, remaining))

    return walk(0, targetSum)

Tìm kiếm theo chiều sâu với ngăn xếp tường minh

Ý tưởng

Mỗi lần gọi đệ quy giữ một số. Thay vào đó, hãy tự giữ số đó trong ngăn xếp bên cạnh mỗi nút: tổng của đường đi từ gốc đến nút đó. Bắt đầu với (0, tree[0]); mỗi nút con nhận tổng của nút cha cộng với giá trị của chính nó. Lấy một cặp ra khỏi ngăn xếp. Nếu nút đó là nút lá có tổng bằng targetSum, bạn đã hoàn thành; nếu không, hãy thêm các nút con thực của nó vào ngăn xếp.

Mỗi nút thực được thêm vào ngăn xếp một lần, độ phức tạp thời gian O(n), và ngăn xếp chứa khoảng một nút anh em đang chờ ở mỗi cấp, O(h). Cùng vòng lặp đó cũng hoạt động với cây sâu dùng con trỏ, nơi đệ quy có thể làm cạn ngăn xếp.

Thuật toán

Đẩy (0, tree[0]) vào ngăn xếp.
Lấy một cặp (i, total) ra khỏi ngăn xếp và kiểm tra các vị trí con 2*i+1 và 2*i+2.
Nếu cả hai vị trí con đều không có nút thực và total bằng targetSum, trả về true.
Đẩy mỗi nút con thực c vào ngăn xếp dưới dạng (c, total + tree[c]).
Khi ngăn xếp trống, trả về false.

def hasPathSum(tree, targetSum):
    n = len(tree)
    stack = [(0, tree[0])]  # (node index, sum of the path from the root to it)
    while stack:
        i, total = stack.pop()
        left, right = 2 * i + 1, 2 * i + 2
        has_left = left < n and tree[left] != -1
        has_right = right < n and tree[right] != -1
        if not has_left and not has_right and total == targetSum:
            return True  # a leaf whose path adds up
        if has_left:
            stack.append((left, total + tree[left]))
        if has_right:
            stack.append((right, total + tree[right]))
    return False

Lỗi thường gặp và trường hợp biên

So sánh tổng tại mọi nút. Trong ví dụ thứ hai, 3 + 9 = 12 khớp tại nút 9, nút này có nút con, nên kết quả là false.
Để vị trí nút con trống kết thúc một đường đi. Khi đó, nút 9 trong ví dụ thứ hai kết thúc một đường đi qua vị trí nút con bên trái đang trống.
Quên xét riêng nút gốc. Một nút duy nhất là nút lá, nên [4] với target 4 cho kết quả true, và [0] với target 0 cũng vậy.
Đọc quá cuối mảng. Nút lá gần cuối có thể có chỉ số nút con vượt quá phần tử cuối cùng.
Nhầm lẫn về độ lệch trong Lua và R. Giữ chỉ số nút bắt đầu từ 0 cho 2*i+1 và đọc tree[i + 1].

Câu hỏi thường gặp3

Độ phức tạp thời gian của Path Sum là bao nhiêu?

O(n): mỗi nút được duyệt nhiều nhất một lần và quá trình tìm kiếm có thể dừng lại ở lá đầu tiên khớp. Không gian bổ sung là O(h) cho đường đi đang được khám phá, dưới dạng các khung gọi hàm hoặc các phần tử trên ngăn xếp của riêng bạn.

Có thể giải bài toán tổng đường đi bằng BFS không?

Có. Thay vì dùng ngăn xếp, hãy đưa các cặp gồm một nút và tổng đường đi của nút đó vào hàng đợi, rồi kiểm tra từng nút lá khi lấy nút đó ra. Độ phức tạp thời gian vẫn là O(n), nhưng hàng đợi có thể chứa cả một tầng, khoảng một nửa số nút của cây đầy đủ, trong khi ngăn xếp chỉ chứa khoảng một nút cho mỗi tầng.

Làm thế nào để tìm mọi đường đi có tổng bằng targetSum?

Hãy giữ danh sách các nút trên đường đi hiện tại khi bạn đi xuống, sao chép danh sách đó vào đáp án ở mỗi nút lá có tổng khớp, rồi xóa nút cuối cùng khi bạn quay ngược lên. Cách duyệt vẫn giữ nguyên. Việc sao chép các đường đi có thể tốn nhiều chi phí hơn cả việc duyệt khi có nhiều nút lá khớp.

def hasPathSum(tree, targetSum):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

tree = [3, 9, 6, -1, 2, 1, 7]
targetSum = 14

Đầu ra mong đợi

true