एक बाइनरी ट्री को देखते हुए, पेड़ में दिए गए दो नोड्स के सबसे कम सामान्य पूर्वज (LCA) का पता लगाएं।

विकिपीडिया पर एलसीए की परिभाषा के अनुसार: "सबसे कम सामान्य पूर्वज को दो नोड्स पी और क्यू के बीच टी में सबसे कम नोड के रूप में परिभाषित किया गया है जिसमें पी और क्यू दोनों वंशज हैं (जहां हम नोड को स्वयं के वंशज होने की अनुमति देते हैं)। "

उदाहरण १) इनपुट: रूट = [३,५,१,६,२,०,८, नल, नल, ७,४], पी = ५, क्यू = १ आउटपुट: ३ स्पष्टीकरण: नोड्स ५ और १ का एलसीए 3 है

उदाहरण 2) इनपुट: रूट = [3,5,1,6,2,0,8, नल, नल, 7,4], पी = 5, क्यू = 4 आउटपुट: 5 स्पष्टीकरण: नोड्स 5 और 4 का एलसीए 5 है, क्योंकि एलसीए परिभाषा के अनुसार एक नोड स्वयं का वंशज हो सकता है।

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

var lowestCommonAncestor = function(root, p, q) {
    let stack = [root] 
    let hash = new Map()
    
    while (stack.length) {
        let node = stack.pop() 
       
        
        if (node.right) {
            hash[node.right.val] = node.val
            stack.push(node.right)
        }
        
        if (node.left) {
            hash[node.left.val] = node.val
            stack.push(node.left)
        }
    }

    
    let path1 = [q.val, hash[q.val]]
    let path2 = [p.val, hash[p.val]]
   
    while (path1[path1.length - 1] !== root.val) { 
        path1.push(hash[path1[path1.length - 1]])
    }
    
     while (path2[path2.length - 1] !== root.val) {
        path2.push(hash[path2[path2.length - 1]])
    }
    
  
    for (let i = 0; i < path1.length; i ++) {
        let num = path1[i]
        if (path2.indexOf(num) !== -1) {
            console.log(num)
            return num
        }
        
    }
  
};

Myinput: [३,५,१,६,२,०,०,८, अशक्त, अशक्त, ७,४], ७, ८

स्टडआउट: 3 (सही)

आउटपुट: अपरिभाषित

1
Daniel Lancaster 18 फरवरी 2021, 21:41

2 जवाब

सबसे बढ़िया उत्तर

मुख्य समस्या यह है कि आपको सबसे कम सामान्य पूर्वज को वापस करने के लिए कहा जाता है: यह एक मान नहीं है, बल्कि एक नोड है। तो आपको val संपत्ति नहीं लौटानी चाहिए, लेकिन नोड ऑब्जेक्ट जिसमें वह संपत्ति है।

इसका वास्तव में मतलब है कि आपको अपने कोड से val संपत्तियों के सभी संदर्भ हटा देने चाहिए: वे अप्रासंगिक हैं।

आपके कोड में दो और समस्याएं हैं:

  • एक Map ऑब्जेक्ट में set और get तरीके होते हैं। आप इसके बजाय उस वस्तु पर स्ट्रिंग गुण बना रहे हैं। यह काम करता है क्योंकि आप val द्वारा कुंजी करते हैं, लेकिन उपरोक्त अवलोकन के बाद, आपको नोड ऑब्जेक्ट द्वारा कुंजी की आवश्यकता होगी, और इसलिए आपको वास्तव में Map.get और Map.set विधियों का ठीक से उपयोग करने की आवश्यकता है।

  • आप path1 और path2 को 2 मानों के साथ इनिशियलाइज़ करते हैं। लेकिन यह समस्या तब देगा जब p या q तर्कों में से कोई एक मूल ही हो। आपको path1 और path2 को केवल एक तत्व से शुरू करना चाहिए। लूप बाकी काम करेगा।

तो यहां आपका कोड सही किया गया है:

var lowestCommonAncestor = function(root, p, q) {
    let stack = [root];
    let hash = new Map();

    while (stack.length) {
        let node = stack.pop(); 

        if (node.right) {
            hash.set(node.right, node);
            stack.push(node.right);
        }

        if (node.left) {
            hash.set(node.left, node);
            stack.push(node.left);
        }
    }


    let path1 = [q];
    let path2 = [p];

    while (path1[path1.length - 1] !== root) { 
        path1.push(hash.get(path1[path1.length - 1]));
    }

    while (path2[path2.length - 1] !== root) {
        path2.push(hash.get(path2[path2.length - 1]));
    }

    for (let i = 0; i < path1.length; i ++) {
        let node = path1[i];
        if (path2.indexOf(node) !== -1) {
            return node;
        }
    }
}

एनबी: कृपया अर्धविराम के साथ बयान समाप्त करने की आदत का प्रयोग करें। वास्तव में कोई अच्छा कारण नहीं है कि आप इसे स्वचालित अर्धविराम प्रविष्टि एल्गोरिथम। आप इसके जाल में फंसने वाले पहले व्यक्ति नहीं होंगे।

1
trincot 19 फरवरी 2021, 00:12

हालांकि यह आपके उत्तर में मदद नहीं करेगा, यह समस्या को गलत तरीके से पढ़ने का एक दिलचस्प परिणाम है। मैंने सोचा था कि पेड़ों को केवल उन सरणियों द्वारा दर्शाया गया था। यह किया जा सकता है, और हम निश्चित रूप से दो संरचनाओं के बीच आगे और पीछे परिवर्तित कर सकते हैं इंडेक्स n पर नोड के बच्चे 2n + 1 और 2n + 2 और इंडेक्स पर नोड के पैरेंट होने के नाते n (n > 0 के लिए) (n-1) >> 1 होने के नाते।

तो उस समस्या को हल करना काफी सरल है:

const paths = (n) => 
  [n, ...(n > 0 ? paths ((n - 1) >> 1) : [])]

const intersection = (xs, ys) => 
  xs .filter (x => ys .includes (x))

const lowestCommonAncestor = (xs, p, q) =>
  xs [Math .max (... intersection (paths (xs .indexOf(p)), paths(xs .indexOf (q))))]

console .log (
  lowestCommonAncestor ([3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], 5, 4)
)
console .log (
  lowestCommonAncestor ([3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], 5, 1)
)

लेकिन इसका वास्तविक समस्या से कोई लेना-देना नहीं है जिसमें एक वास्तविक पेड़ में val और वैकल्पिक रूप से left और right गुण हैं। ट्रिंकॉट ने मूल समस्या का अच्छी तरह उत्तर दिया।

0
Scott Sauyet 19 फरवरी 2021, 00:00