Tìm đường dẫn trong cây tìm kiếm nhị phân tổng hợp thành giá trị đích

Question

Cho cây tìm kiếm nhị phân và giá trị đích, tìm tất cả đường dẫn (nếu có nhiều hơn một) tổng giá trị mục tiêu. Nó có thể là bất kỳ con đường nào trong cây. Nó không phải là từ gốc.

Ví dụ, trong cây tìm kiếm nhị phân sau:

2 
/\ 
1 3 

khi tổng nên 6, con đường 1 -> 2 -> 3 sẽ được in.

Answer 1

Di chuyển qua cây từ gốc và thực hiện thu thập sau tất cả các tổng số đường dẫn. Sử dụng một hashtable để lưu trữ các đường dẫn có thể bắt nguồn từ một nút và đi xuống chỉ. Chúng ta có thể xây dựng tất cả các đường dẫn đi qua một nút từ chính nó và các đường dẫn của trẻ em.

Dưới đây là mã psuedo thực hiện ở trên, nhưng chỉ lưu trữ số tiền chứ không phải đường dẫn thực tế. Đối với các đường dẫn, bạn cần lưu trữ nút kết thúc trong hashtable (chúng ta biết nó bắt đầu ở đâu và chỉ có một đường dẫn giữa hai nút trong một cây).

function findsum(tree, target) 
    # Traverse the children 
    if tree->left 
    findsum(tree.left, target) 
    if tree->right 
    findsum(tree.right, target) 

    # Single node forms a valid path 
    tree.sums = {tree.value} 

    # Add this node to sums of children 
    if tree.left 
    for left_sum in tree.left.sums 
     tree.sums.add(left_sum + tree.value) 
    if tree.right 
    for right_sum in tree.right.sums 
     tree.sums.add(right_sum + tree.value) 

    # Have we formed the sum? 
    if target in tree.sums 
    we have a path 

    # Can we form the sum going through this node and both children? 
    if tree.left and tree.right 
    for left_sum in tree.left.sums 
     if target - left_sum in tree.right.sums 
     we have a path 

    # We no longer need children sums, free their memory 
    if tree.left 
    delete tree.left.sums 
    if tree.right 
    delete tree.right.sums 

Điều này không sử dụng thực tế là cây là cây tìm kiếm, vì vậy nó có thể được áp dụng cho bất kỳ cây nhị phân nào.

Đối với những cây lớn, kích thước của thẻ bắt đầu bằng tay sẽ không thể phát triển được. Nếu chỉ có các giá trị dương, nó có thể hiệu quả hơn khi sử dụng một mảng được chỉ mục bởi tổng.

Answer 2

Câu trả lời của tôi là O(n^2), nhưng tôi tin rằng câu trả lời là chính xác và mất hơi cách tiếp cận khác nhau và có vẻ dễ triển khai hơn.

Giả sử giá trị được lưu trữ tại nút i được biểu thị bằng VALUE[i]. Ý tưởng của tôi là lưu trữ tại mỗi nút tổng của các giá trị trên đường dẫn từ root đến nút đó. Vì vậy, đối với mỗi nút i, SUM[i] là tổng của đường dẫn từ root đến nút i.

Sau đó cho mỗi cặp nút (i,j), hãy tìm tổ tiên chung của chúng k. Nếu SUM(i)+SUM(j)-SUM(k) = TARGET_SUM, bạn đã tìm thấy câu trả lời.

Đây là O(n^2) vì chúng tôi đang lặp qua tất cả các cặp nút. Mặc dù, tôi ước tôi có thể tìm ra cách tốt hơn là chỉ chọn tất cả các cặp.

Chúng tôi có thể tối ưu hóa nó một chút bằng cách loại bỏ các subtrees trong đó value của nút được bắt nguồn từ cây con lớn hơn TARGET_SUM. Bất kỳ tối ưu hóa hơn nữa được hoan nghênh :)

psuedocode:

# Skipping code for storing sum of values from root to each node i in SUM[i] 
for i in nodes: 
    for j in nodes: 
     k = common_ancestor(i,j) 
     if (SUM[i] + SUM[j] - SUM[k] == TARGET_SUM): 
      print_path(i,k,j) 

Chức năng common_ancestor là một vấn đề khá tiêu chuẩn cho một cây tìm kiếm nhị phân. Psuedocode (từ bộ nhớ, hy vọng không có lỗi!):

sub common_ancestor (i, j): 
    parent_i = parent(i) 
    # Go up the parent chain until parent's value is out of the range. 
    # That's a red flag. 
    while(VAL[i] <= VAL[parent_i] <= VAL[j]) : 
    last_parent = parent_i 
    parent_i = parent(i) 
    if (parent_i == NULL): # root node 
     break 
return last_parent 

Answer 3

Cũ câu hỏi, nhưng đây là đâm của tôi lúc đó - nên O (n) thời gian như bạn ghé thăm mỗi nút một lần duy nhất:

public static List<ArrayList<Integer>> pathSum(Node head, int sum) { 
    List<Integer> currentPath = new ArrayList<Integer>(); 
    List<ArrayList<Integer>> validPaths = new ArrayList<ArrayList<Integer>>(); 

    dfsSum(head, sum, currentPath, validPaths); 

    return validPaths; 
    } 

    public static void dfsSum(Node head, int sum, List<Integer> currentPath, List<ArrayList<Integer>> validPaths) { 
    if (head == null) return; 

    currentPath.add(head.val); 

    if (head.left == null && head.right == null && sum == head.val) { 
     validPaths.add(new ArrayList<Integer>(currentPath)); 
    } 

    dfsSum(head.left, sum - head.val, new ArrayList<Integer>(currentPath), validPaths); 
    dfsSum(head.right, sum - head.val, new ArrayList<Integer>(currentPath), validPaths); 
    } 

Và lớp nút:

class Node { 
    public int val; 
    public Node left; 
    public Node right; 

    public Node(int val) { 
     this.val = val; 
    } 
    }