एक लक्ष्य मूल्य

Question

को एक बाइनरी खोज पेड़ में पथ खोजें, बाइनरी खोज पेड़ और लक्ष्य मान को देखते हुए, सभी पथ खोजें (यदि एक से अधिक मौजूद है) जो लक्ष्य मान तक पहुंचते हैं। यह पेड़ में कोई रास्ता हो सकता है। यह जड़ से नहीं होना चाहिए।

उदाहरण के लिए, निम्नलिखित द्विआधारी खोज वृक्ष में:

2 
/\ 
1 3 

जब योग 6 होना चाहिए, पथ 1 -> 2 -> 3 मुद्रित किया जाना चाहिए।

Answer 1

रूट से पेड़ के माध्यम से ट्रैव करें और सभी पथों की एक पोस्ट-ऑर्डर एकत्रण करें। किसी नोड पर रूट किए गए संभावित पथों को स्टोर करने और केवल नीचे जाने के लिए हैशटेबल का उपयोग करें। हम अपने और अपने बच्चों के पथ से नोड के माध्यम से जाने वाले सभी मार्गों का निर्माण कर सकते हैं।

यहां psuedo-code है जो उपर्युक्त लागू करता है, लेकिन केवल वास्तविक रकम स्टोर करता है, बल्कि वास्तविक पथों को संग्रहीत करता है। पथों के लिए, आपको हैशटेबल में अंत नोड को स्टोर करने की आवश्यकता है (हम जानते हैं कि यह कहां से शुरू होता है, और पेड़ में दो नोड्स के बीच केवल एक ही पथ है)।

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 

यह इस तथ्य का उपयोग नहीं करता है कि पेड़ एक खोज पेड़ है, इसलिए इसे किसी भी बाइनरी पेड़ पर लागू किया जा सकता है।

बड़े पेड़ों के लिए, हैशटेबल का आकार हाथ से बाहर हो जाएगा। यदि केवल सकारात्मक मूल्य हैं, तो यह राशि द्वारा अनुक्रमित सरणी का उपयोग करने के लिए और अधिक कुशल हो सकता है।

Answer 2

मेरा उत्तर O(n^2) है, लेकिन मुझे लगता है कि यह सही है, और थोड़ा अलग दृष्टिकोण लेता है और इसे लागू करने में आसान लग रहा है।

मान लें कि नोड i पर संग्रहीत मान VALUE[i] द्वारा दर्शाया गया है। मेरा विचार है कि प्रत्येक नोड को उस नोड पर root से पथ पर मानों के योग को स्टोर करना है। इसलिए प्रत्येक नोड i, SUM[i]root से i नोड के पथ का योग है।

फिर प्रत्येक नोड जोड़ी (i,j) के लिए, उनके सामान्य पूर्वजों k खोजें। यदि SUM(i)+SUM(j)-SUM(k) = TARGET_SUM, आपको एक उत्तर मिला है।

यह O(n^2) है क्योंकि हम सभी नोड जोड़े पर लूपिंग कर रहे हैं। हालांकि, मेरी इच्छा है कि मैं सिर्फ सभी जोड़ों को चुनने से बेहतर तरीके से पता लगा सकूं।

हम सबट्री को छोड़कर इसे थोड़ा सा अनुकूलित कर सकते हैं जहां value उपट्री में रूट नोड के TARGET_SUM से अधिक है। किसी भी आगे अनुकूलन स्वागत है :)

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) 

समारोह common_ancestor एक द्विआधारी खोज वृक्ष के लिए एक सुंदर मानक समस्या है। Psuedocode (स्मृति से, उम्मीद है कि कोई त्रुटि नहीं है!):

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

पुराना सवाल है, लेकिन यहां इस पर मेरी वार है - हे (एन) समय अपने प्रत्येक नोड केवल एक बार की यात्रा के रूप में किया जाना चाहिए:

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); 
    } 

और नोड वर्ग:

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

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