लिस्ट ऑफ़ डेप्थ्स: पेड़ के हर स्तर पर एक लिंक्ड लिस्ट (जावा)

टीएल;डीआर

समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।

दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली की समस्या ४.३: बाइनरी ट्री को गहराई-दर-गहराई लिंक्ड लिस्टों की सूची में बदलो। पहले बीएफएस स्तर-क्रम, वैकल्पिक डीएफएस गहराई सूचकांक के साथ, साफ जावा में।

जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।

एक इमारत में मंज़िलें होती हैं। मंज़िल ० पर सब एक समूह। मंज़िल १ पर सब दूसरा समूह। बाइनरी ट्री में भी वही बात: गहराई ० सिर्फ जड़ है, गहराई १ जड़ के बच्चे हैं, और आगे। काम पेड़ को बेतरतीब घूमना नहीं। हर गहराई के लिए नोडों की एक सूची बनानी है, ताकि बिना दोबारा घूमे "इस स्तर पर सब" सौंप सको।

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

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

ऑफिस बिल्डिंग सोचो जहाँ लोग पेड़ की तरह बैठे हों:

मंज़िल ०: सीईओ (जड़)।
मंज़िल १: दो सीधे रिपोर्ट।
मंज़िल २: उनके रिपोर्ट, और आगे।

मानव संसाधन को हर मंज़िल का क्लिपबोर्ड चाहिए: उस मंज़िल पर खड़े सबकी लिंक्ड लिस्ट, बाएँ से दाएँ अगर स्तरों से स्कैन करो।

तुम कर सकते हो:

१. मंज़िल-दर-मंज़िल मौजूदा मंज़िल की कतार से चलो (बीएफएस)। मंज़िल क पर सबको प्रोसेस करो, क्लिपबोर्ड क पर लिखो, फिर उनके बच्चों को मंज़िल क+१ के लिए कतार में डालो। २. एक-एक व्यक्ति मिलो और मंज़िल नंबर वाला नोट चिपकाओ (डीएफएस)। मंज़िल द पर किसी को पाते ही क्लिपबोर्ड द पर जोड़ो। अगर अभी नहीं बना तो बनाओ।

दोनों का अंत एक ही आकार: सूचियों की सूची, सूचकांक = गहराई।

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

इनपुट: बाइनरी ट्री की जड़ (null अगर पेड़ खाली)।

आउटपुट: नोडों की लिंक्ड लिस्टों की सूची। प्रविष्टि i पर गहराई i के सभी नोड, आमतौर पर बाएँ से दाएँ अगर बीएफएस इस्तेमाल करो।

अगर पेड़ की ऊँचाई एच है (सबसे लंबे जड़-से-पत्ती रास्ते पर किनारे), तो एच+१ सूचियाँ मिलती हैं (गहराई ० से एच)। खाली पेड़ बाहरी खाली सूची देता है।

नोड का आकार:

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;

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

उदाहरण:

अपेक्षित (मान दिखाए; सूचियाँ नोड ऑब्जेक्ट रखती हैं):

गहराई	सूची (बाएँ से दाएँ)
०	४
१	२ → ६
२	१ → ३ → ७

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

नोड संदर्भों की लिंक्ड लिस्ट, या मानों की प्रति? (पेड़ के नोडों के संदर्भ, जब तक इंटरव्यूअर कुछ और न कहे।)
स्तर के अंदर क्रम? (आमतौर पर बाएँ से दाएँ। बीएफएस मुफ्त में देता है।)
java.util.LinkedList / ArrayList चल सकते हैं? (इस सीरीज़ में हाँ।)
खाली पेड़ और एक-नोड वाला पेड़?

३. पहले सोचो

तरीका क: बीएफएस स्तर-क्रम (मुख्य)

यह स्वाभाविक फिट है। स्तर-क्रम ट्रैवर्सल पहले से गहराई से समूह बनाता है।

१. अगर root है null, खाली परिणाम लौटाओ। २. जड़ को कतार में डालो। ३. जब तक कतार खाली न हो:

नोट करो levelSize = queue.size() (अभी इस गहराई पर कितने नोड)।
इस गहराई के लिए नई लिंक्ड लिस्ट बनाओ।
levelSize बार दोहराओ: नोड निकालो, स्तर-सूची में जोड़ो, बायाँ-दायाँ बच्चे हों तो कतार में डालो।
स्तर-सूची परिणाम में जोड़ो।

levelSize क्यों? उसके बिना नहीं पता एक गहराई कहाँ खत्म और अगली कहाँ शुरू, क्योंकि कतार में अगले स्तर के बच्चे भी होते हैं।

तरीका ख: गहराई वाला डीएफएस (वैकल्पिक)

(node, depth) के साथ पुनरावृत्ति:

१. बाहरी List<LinkedList<TreeNode>> रखो। २. गहराई d पर नोड मिलते ही, अगर result.size() == d, नई खाली लिंक्ड लिस्ट जोड़ो (इस गहराई के पहले आगंतुक हो)। ३. नोड को result.get(d) में जोड़ो। ४. बाएँ d + 1 से, फिर दाएँ d + 1 से पुनरावृत्ति।

भेंट क्रम प्रीऑर्डर (जड़, बायाँ, दायाँ)। स्तर के अंदर बाएँ-से-दाएँ तब भी रहता है जब हमेशा बाएँ पहले जाओ।

डीएफएस तब काम आता है जब पहले से पुनरावृत्ति सोचते हो, या साफ कतार से बचना हो। "हर स्तर एक सूची" इंटरव्यू में बीएफएस अक्सर साफ रहता है।

क्या न करो

सब नोडों की एक विशाल सूची बनाकर बाद में बिना गहराई रखे तोड़ना। समूह खो गया।
पेड़ के left/right पॉइंटर घुमाकर सूचियाँ बनाना। समस्या नई नोड-सूचियाँ चाहती है, टूटा पेड़ नहीं (जब तक न माँगा हो)।

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

बीएफएस (मुख्य)

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class ListOfDepths {
    public static List<LinkedList<TreeNode>> createLevelLists(TreeNode root) {
        List<LinkedList<TreeNode>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            LinkedList<TreeNode> level = new LinkedList<>();

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.remove();
                level.add(node);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }

            result.add(level);
        }

        return result;
    }
}

नमूना पेड़ पर चलान:

कदम	स्तर से पहले कतार	levelSize	बनी स्तर सूची	कतार में बच्चे
१	[४]	१	४	२, ६
२	[२, ६]	२	२ → ६	१, ३, फिर ७
३	[१, ३, ७]	३	१ → ३ → ७	(कोई नहीं)
४	खाली	रुक

परिणाम का आकार ३। गहराई ०, १, २।

डीएफएस (वैकल्पिक)

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

class ListOfDepthsDfs {
    public static List<LinkedList<TreeNode>> createLevelLists(TreeNode root) {
        List<LinkedList<TreeNode>> result = new ArrayList<>();
        createLevelLists(root, 0, result);
        return result;
    }

    private static void createLevelLists(
            TreeNode node,
            int depth,
            List<LinkedList<TreeNode>> result) {
        if (node == null) {
            return;
        }

        if (result.size() == depth) {
            result.add(new LinkedList<TreeNode>());
        }

        result.get(depth).add(node);
        createLevelLists(node.left, depth + 1, result);
        createLevelLists(node.right, depth + 1, result);
    }
}

वही नमूना, प्रीऑर्डर जोड़ क्रम: ४, फिर २, १, ३, फिर ६, ७। अंत में:

गहराई ०: [४]
गहराई १: [२, ६]
गहराई २: [१, ३, ७]

बीएफएस जैसा ही समूह।

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

तरीका	समय	अतिरिक्त स्थान (आउटपुट के अलावा)
बीएफएस स्तर-क्रम	ओ(एन)	ओ(डब्ल्यू) कतार, डब्ल्यू = पेड़ की अधिकतम चौड़ाई
डीएफएस पुनरावृत्ति	ओ(एन)	ओ(एच) कॉल स्टैक, एच = ऊँचाई

एन नोडों की संख्या है। हर नोड एक बार छूते और एक बार जोड़ते हो, इसलिए समय रैखिक।

आउटपुट स्थान दोनों में ओ(एन): हर नोड ठीक एक भीतरी सूची में आता है। यह समस्या की माँग है, वैकल्पिक बोझ नहीं।

पूर्ण पेड़ में निचले स्तर पर अधिकतम चौड़ाई लगभग एन/२ होती है, इसलिए बीएफएस कतार Θ(एन) हो सकती है। पतले पेड़ (हमेशा एक बच्चा) में कतार छोटी रहती है और डीएफएस स्टैक Θ(एन)।

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

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

खाली पेड़ (root == null) → बाहरी खाली सूची, अंदर एक खाली सूची वाली सूची नहीं।
एक नोड → सिर्फ उसी नोड वाली एक सूची।
असंतुलित पेड़ → गहरी तरफ अपनी गहरी सूचियाँ मिलती हैं; गायब भाई बस नहीं आते।
बाएँ या दाएँ तिरछा → मौजूद हर गहराई पर एक सूची; हर गहराई पर आकार १।
दोहरे मान → सूचियाँ नोड संदर्भ रखती हैं, इसलिए data == 5 वाले दो नोड अलग प्रविष्टियाँ हैं।

आम गलतियाँ:

१. बीएफएस में levelSize भूलना। एक पास में गहराइयाँ मिल जाती हैं, या सेंटीनेल/null हैक चाहिए। २. बिना जाँच null बच्चे कतार में डालना, फिर उन्हें असली नोड समझकर एनपीई। ३. डीएफएस में बाहरी सूची बढ़ाए बिना गहराई को इंडेक्स मानना। गहराई द पहली बार मिले तो सूची बनानी होगी। ४. हस्ताक्षर नोड माँगे तो मान लौटाना (या उल्टा)। ५. left/right को लिंक्ड लिस्ट में जोड़कर मूल पेड़ तोड़ना। ६. गहराई बनाम ऊँचाई पर एक-की-गलती। जड़ की गहराई ०। गैर-खाली पेड़ में सूचियों की संख्या = ऊँचाई + १।

छोटा उपयोग स्केच:

TreeNode root = new TreeNode(4);
root.left = new TreeNode(2);
root.right = new TreeNode(6);
// ... 1, 3, 7 जोड़ो

List<LinkedList<TreeNode>> levels = ListOfDepths.createLevelLists(root);
// levels.get(0) है 4
// levels.get(1) है 2 → 6
// levels.get(2) है 1 → 3 → 7

७. दोस्त को समझाओ सार

लिस्ट ऑफ़ डेप्थ्स है "पेड़ के नोडों को मंज़िल नंबर से समूहित करो":

१. बीएफएस: कतार को स्तर-आकार के बैच में प्रोसेस करो। हर बैच एक लिंक्ड लिस्ट। बच्चे अगले बैच का इंतज़ार करते हैं। २. डीएफएस: पुनरावृत्ति में गहराई भेजो। हर नोड lists.get(depth) में जोड़ो। उस गहराई पर पहली बार पहुँचते ही सूची बनाओ। ३. खाली पेड़ → कोई सूची नहीं। सिर्फ जड़ → एक नोड की एक सूची। ४. समय ओ(एन)। अतिरिक्त स्थान कतार की चौड़ाई या पुनरावृत्ति की ऊँचाई, साथ आउटपुट सूचियाँ।

अगर मंज़िलें खींच सको, बिना देखे बीएफएस का levelSize लूप लिख सको, और एक किनारा मामला (null जड़) नाम ले सको, तो समस्या ४.३ तुम्हारी है।