पाथ्स विद सम: नीचे की ओर वे रास्ते गिनो जो लक्ष्य योग दें (जावा)

टीएल;डीआर

• समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।
• दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली की समस्या ४.१२: द्विआधारी वृक्ष में हर वह रास्ता गिनो जिसका योग लक्ष्य के बराबर हो। सिर्फ माता-पिता से बच्चे की ओर। हर नोड से ब्रूट फोर्स, फिर चल योग और उपसर्ग गिनती का हैशमैप।
• जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।

पहाड़ की पगडंडी पर उतर रहे हो। हर मोड़ पर एक संख्या: चढ़ाई या गिरावट। तुम्हें हर वह खंड चाहिए जिसका कुल बदलाव किसी लक्ष्य के बराबर हो, मान लो ८। खंड पगडंडी के बीच से शुरू हो सकता है, बीच में खत्म हो सकता है, और ऊपर वापस नहीं चढ़ता। यही द्विआधारी वृक्ष पर पाथ्स विद सम है: सिर्फ माता-पिता से बच्चे की ओर, कोई भी शुरुआत, कोई भी अंत।

यह पोस्ट जावा में शुरुआती लोगों के लिए मूल शिक्षण है। इंटरव्यू वाली वृक्ष-रास्ता-योग समस्याओं का परिवार, किताब की नकल नहीं। सीटीसीआई जावा सीरीज़ का हिस्सा। अध्याय ४, ट्री और ग्राफ, यहीं खत्म होता है।

---

१. रोज़मर्रा की उपमा

जमा-निकासी का पारिवारिक वृक्ष सोचो। हर व्यक्ति के ऊपर एक माता-पिता, नीचे दो तक बच्चे। व्यक्ति पर पैसा उसकी लेन-देन है।

यहाँ रास्ता कोई भी रिश्ता नहीं। सीधी नीचे की सैर है: दादा से माता-पिता से बच्चे। बग़ल में कूदना नहीं। ऊपर चढ़ना नहीं।

किसी भी व्यक्ति को शुरुआत चुनो और किसी भी वंशज को अंत (शुरुआत अकेले भी)। उस नीचे की श्रृंखला के मान जोड़ो। योग लक्ष्य के बराबर हो तो गिनो।

लक्ष्य 8 का उदाहरण:

        10
       /  \
      5   -3
     / \    \
    3   2   11
   / \   \
  3  -2   1

तीन रास्ते ८ देते हैं:

• 5 → 3
• 5 → 2 → 1
• -3 → 11

10 → 5 है १५, नहीं गिना। अकेला नोड मान ८ भी गिना जाता।

---

२. समस्या सादे शब्दों में

इनपुट: द्विआधारी वृक्ष की जड़। हर नोड में int (धनात्मक, ऋणात्मक या शून्य)। पूर्णांक targetSum।

आउटपुट: नीचे की ओर उन रास्तों की संख्या जिनके नोड मानों का योग targetSum हो।

नियम:

• रास्ता सिर्फ माता-पिता → बच्चा (नीचे)।
• किसी भी नोड से शुरू, सिर्फ जड़ नहीं।
• किसी भी नोड पर खत्म, सिर्फ पत्ती नहीं।
• एक अकेला नोड लंबाई १ का वैध रास्ता है।
• ऋणात्मक मान हो सकते हैं, इसलिए "योग पहले से बहुत बड़ा" कहकर जल्दी नहीं काट सकते।

नोड का आकार:

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

उदाहरण:

वृक्ष का विचार	लक्ष्य	गिनती	क्यों
ऊपर वाला वृक्ष	८	३	5→3, 5→2→1, -3→11
अकेला नोड 8	८	१	नोड अकेला
अकेला नोड 1	८	०	कोई रास्ता ८ नहीं
जड़ null	कुछ भी	०	खाली वृक्ष
सिर्फ 1 → 2 → 3	३	आकार पर निर्भर	जो खंड ३ जोड़ें

कोड से पहले स्पष्ट करो:

• ऋणात्मक मान? (हाँ। साधारण जल्दी-काट बंद।)
• ओवरलैप रास्ते अलग गिने? (हाँ।)
• लगातार नीचे? (हाँ। बीच का बच्चा छोड़ना नहीं।)
• रास्ते लौटाएँ या सिर्फ गिनती? (सिर्फ गिनती।)

---

३. पहले सोचो

ब्रूट: हर नोड संभावित शुरुआत

हर नोड u पर डीएफएस चलाओ जो u से शुरू होकर सिर्फ नीचे जाए। चल योग रखो। जब योग लक्ष्य के बराबर हो, उत्तर बढ़ाओ। हिट के बाद भी चलते रहो: लंबा रास्ता फिर हिट कर सकता है (ऋणात्मक हैं)।

समय: एन नोड में से हर एक से तिरछे वृक्ष में ओ(एन) वंशज, सबसे खराब ओ(एन²)। संतुलित वृक्ष पर लगभग ओ(एन लॉग एन)। स्थान ओ(एच) रिकर्शन ऊँचाई।

पहला जवाब ठीक। इंटरव्यू में अक्सर अगला रैखिक पास चाहते हैं।

अनुकूलित: चल योग + उपसर्ग गिनती

एक-आयामी सारणी में "कितने सबऐरे लक्ष्य जोड़ें" उपसर्ग योग के मैप से होता है। वृक्ष में सिर्फ नीचे जाने वाला रास्ता जड़-से-पत्ती रीढ़ पर सबऐरे जैसा है, पर खंड बीच से शुरू हो सकता है।

किसी नोड पर runningSum परिभाषित करो: पूरे वृक्ष की जड़ से इस नोड तक मानों का योग (डीएफएस का सक्रिय रास्ता)।

अगर किसी पूर्वज का उपसर्ग S था और अभी runningSum है, तो उस पूर्वज के नीचे से यहाँ तक का खंड runningSum - S जोड़ता है।

चाहिए runningSum - S == targetSum, यानी S == runningSum - targetSum।

HashMap<Integer, Integer> रखो: वर्तमान जड़-से-यहाँ रास्ते पर हर उपसर्ग योग कितनी बार आया। हर नोड पर:

१. मैप में runningSum - targetSum देखो। यही गिनती बताती है कितने रास्ते यहीं खत्म होते हैं और लक्ष्य जोड़ते हैं। २. runningSum की एंट्री में १ जोड़ो। ३. बाएँ-दाएँ पुनरावृत्ति। ४. बैकट्रैक: runningSum से १ घटाओ (शून्य हो तो हटाओ)। भाई उपवृक्षों को यह उपसर्ग नहीं दिखना चाहिए।

चलने से पहले मैप में 0 → 1 डालो। जड़ के ऊपर खाली उपसर्ग। जब runningSum == targetSum हो तो जड़ से शुरू रास्ता भी मिले।

एक डीएफएस हर नोड एक बार। मैप काम प्रति नोड लगभग ओ(१)। समय ओ(एन)। अतिरिक्त स्थान ओ(एच) स्टैक, बैकट्रैक से वर्तमान रास्ते पर अधिकतम ओ(एच) कुंजियाँ (डंडी वृक्ष पर ओ(एन))।

---

४. जावा समाधान

ब्रूट फोर्स (साफ पहला पास)

int countPathsBrute(TreeNode root, int targetSum) {
    if (root == null) {
        return 0;
    }
    return countFrom(root, targetSum)
        + countPathsBrute(root.left, targetSum)
        + countPathsBrute(root.right, targetSum);
}

/** Paths that start at 'node' and go only downward. */
int countFrom(TreeNode node, long remaining) {
    if (node == null) {
        return 0;
    }
    int count = 0;
    if (node.val == remaining) {
        count++;
    }
    count += countFrom(node.left, remaining - node.val);
    count += countFrom(node.right, remaining - node.val);
    return count;
}

remaining (अभी कितना चाहिए) बढ़ते योग जितना ही विचार है। दोनों शैली ठीक।

मुख्य: उपसर्ग मैप (इंटरव्यू लक्ष्य)

import java.util.HashMap;
import java.util.Map;

int countPathsWithSum(TreeNode root, int targetSum) {
    Map<Integer, Integer> prefixCounts = new HashMap<>();
    prefixCounts.put(0, 1); // empty prefix above the root
    return dfs(root, 0, targetSum, prefixCounts);
}

int dfs(TreeNode node, int runningSum, int targetSum, Map<Integer, Integer> prefixCounts) {
    if (node == null) {
        return 0;
    }

    runningSum += node.val;

    int pathsEndingHere = prefixCounts.getOrDefault(runningSum - targetSum, 0);

    prefixCounts.put(runningSum, prefixCounts.getOrDefault(runningSum, 0) + 1);

    int total = pathsEndingHere
        + dfs(node.left, runningSum, targetSum, prefixCounts)
        + dfs(node.right, runningSum, targetSum, prefixCounts);

    int c = prefixCounts.get(runningSum);
    if (c == 1) {
        prefixCounts.remove(runningSum);
    } else {
        prefixCounts.put(runningSum, c - 1);
    }

    return total;
}

नमूना वृक्ष, लक्ष्य 8, जब डीएफएस पहले बाएँ 5 पर पहुँचे (जड़ से योग: 10 + 5 = 15):

कदम	चल योग	देखो चल योग घटा ८	मैप विचार	यहीं खत्म रास्ते
१० पर	१०	२ → ०	१० डालो	०
५ पर	१५	७ → ०	१५ डालो	०
बाएँ ३ पर	१८	१० → १ (जड़ उपसर्ग)	रास्ता 5→3	१
बच्चे ३ पर	२१	१३ → ०		०
-२ पर	१६	८ → ०		०
वापस; २ पर	१७	९ → ०		०
१ पर	१८	१० → १	रास्ता 5→2→1	१
दायाँ -३	७	-१ → ०		०
११ पर	१८	१० → १	रास्ता -3→11	१

कुल ३। बैकट्रैक से मैप सिर्फ सक्रिय डीएफएस रास्ते के पूर्वज दिखाता है।

---

५. जटिलता तालिका

तरीका	समय	अतिरिक्त स्थान	नोट
ब्रूट: हर नोड से डीएफएस	ओ(एन²) खराब, ~ओ(एन लॉग एन) संतुलित	ओ(एच) स्टैक	पहले समझाना आसान
चल योग + हैशमैप उपसर्ग	ओ(एन)	ओ(एच) आम, डंडी पर ओ(एन)	पसंदीदा इंटरव्यू जवाब
सभी जड़-पत्ती सूचियाँ रख स्कैन	ओ(एन²) नकल	ओ(एन) या ज़्यादा	भारी; टालो

एन नोड संख्या। एच ऊँचाई। मैप इसलिए जीतता है क्योंकि हर नोड एक बार स्थिर काम करता है।

---

६. किनारे के मामले और आम गलतियाँ

इंटरव्यूअर ये छूते हैं:

• खाली जड़ → ०।
• अकेला नोड लक्ष्य के बराबर → १। 0 → 1 बीज पर निर्भर।
• अकेला नोड अलग → ०।
• सब ऋणात्मक, धनात्मक लक्ष्य → सब घूमो; जल्दी बाहर नहीं।
• वृक्ष में शून्य → शून्य योग बदले बिना रास्ता लंबा करता है; कई ओवरलैप हिट सच हैं।
• लक्ष्य ० → वास्तविक नोडों के रास्ते जो ० जोड़ें; काल्पनिक खाली रास्ता नहीं। मानक बीज से, जिस नोड का योग किसी पुराने उपसर्ग जितना हो वह असली गैर-खाली खंड गिनता है।
• तिरछी श्रृंखला → मैप और स्टैक ओ(एन); फिर भी सही, समय रैखिक।
• एक रास्ते पर एक ही उपसर्ग दो बार (शून्य या रद्द ऋणात्मक) → मैप गिनती रखता है, बूलियन नहीं।

आम गलतियाँ:

१. मैप बैकट्रैक भूलना। बाएँ उपवृक्ष का उपसर्ग दाएँ में रिसता है। २. prefixCounts.put(0, 1) भूलना। जड़ से शुरू रास्ते कम गिने जाते हैं। ३. योग लक्ष्य के बराबर होते ही रुकना। लंबा रास्ता ऋणात्मक या शून्य से फिर हिट कर सकता है। डीएफएस जारी रखो। ४. माता-पिता सूचक या मनमाना एलसीए रास्ता। समस्या सिर्फ नीचे है। ५. मैप में नोड पहचान, उपसर्ग योग नहीं। कुंजी संख्यात्मक चल योग है। ६. पूर्णांक ओवरफ्लो। इंटरव्यू में अक्सर int काफी; मान बड़े हों तो long बताओ।

कम से कम जाँच:

TreeNode root = new TreeNode(10);
root.left = new TreeNode(5);
root.right = new TreeNode(-3);
root.left.left = new TreeNode(3);
root.left.right = new TreeNode(2);
root.right.right = new TreeNode(11);
root.left.left.left = new TreeNode(3);
root.left.left.right = new TreeNode(-2);
root.left.right.right = new TreeNode(1);

System.out.println(countPathsWithSum(root, 8)); // 3
System.out.println(countPathsWithSum(null, 8)); // 0
System.out.println(countPathsWithSum(new TreeNode(8), 8)); // 1

---

७. दोस्त को समझाने वाला सार

पाथ्स विद सम पूछता है: द्विआधारी वृक्ष में कितने नीचे माता-पिता-से-बच्चे खंड लक्ष्य जोड़ते हैं?

१. ब्रूट: हर नोड से नीचे चलो, लक्ष्य हिट गिनो। सही, अधिकतम ओ(एन²)। २. बेहतर: जड़ से चल योग वाला डीएफएस। वर्तमान रास्ते पर हर उपसर्ग कितनी बार, उसका मैप। ३. हर नोड पर, यहीं खत्म और लक्ष्य हिट रास्ते = मैप में runningSum - target की गिनती। ४. बीज 0 → 1। बच्चों से पहले वर्तमान उपसर्ग बढ़ाओ। बाद में घटाओ (बैकट्रैक)। ५. ऋणात्मक और शून्य: "योग बहुत बड़ा" से मत काटो। सारे ओवरलैप गिने जाते हैं।

नमूना वृक्ष खींच सको, तीन रास्ते ८ क्यों बता सको, और हैशमैप बैकट्रैक क्यों ज़रूरी समझा सको, तो समस्या ४.१२ तुम्हारी है। अध्याय ४ एक वृक्ष सैर पर बंद होता है जो असल में उपसर्ग-योग की चाल है।

---

सीरीज़

• गाइड: सीटीसीआई सीरीज़ गाइड
• पिछला: रैंडम नोड
• अगला: इन्सर्शन