टीएल;डीआर
- समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।
- दृष्टिकोण: टी१, टी२ से बहुत बड़ा है। तय करो कि टी२, टी१ का सबट्री है या नहीं: टी१ में टी२ की जड़ ढूँढो फिर मैचट्री, या नल चिह्नों वाला प्रीऑर्डर स्ट्रिंग और कंटेन्स। जावा, ओ(एन + केएम) बनाम ओ(एन + एम)।
- जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।
तुम्हारे पास एक बड़ा बाइनरी ट्री टी१ है और बहुत छोटा ट्री टी२। सवाल कहने में आसान, गलत होने में भी आसान: क्या टी२, टी१ का सबट्री है? मतलब टी१ का कोई नोड n ऐसा है जिसके नीचे की पूरी शाखा टी२ जैसी हो: वही संरचना, वही मान, पत्तियों तक। n पर काटो तो टी२ मिले, "टी२ जैसी शुरूआत" नहीं।
यह पोस्ट सीटीसीआई जावा सीरीज़ की समस्या ४.१० चेक सबट्री है। मूल शिक्षण, किताब की नकल नहीं। दो ठोस रास्ते: पुनरावर्ती खोज प्लस ट्री मिलान, और नल चिह्नों वाली प्रीऑर्डर स्ट्रिंग।
रोज़मर्रा की तस्वीर
किसी कंपनी का संगठन चार्ट (टी१) और एक टीम की फोटो (टी२) सोचो।
- टी२ सबट्री तभी है जब टी१ का कोई मैनेजर बिल्कुल वही टीम अपने नीचे रखता हो: बाएँ/दाएँ उन्हीं सीटों पर वही लोग, खाली कुर्सियाँ (नल संतान) भी शामिल।
- बड़े चार्ट में कहीं-कहीं वही नाम दिखना काफ़ी नहीं। क्रम और आकार मायने रखते हैं।
- जड़ से पत्ती तक कोई रास्ता टी२ से मिल जाए, यह भी काफ़ी नहीं। सबट्री मतलब किसी नोड के नीचे जड़वाली पूरी आकृति।
तो: टी१ में उम्मीदवार जड़ ढूँढो, फिर साबित करो कि पूरा छोटा ट्री बैठता है। या दोनों ट्री सावधानी से स्ट्रिंग लिखो और पूछो कि छोटी स्ट्रिंग बड़ी के अंदर है या नहीं।
समस्या सादे शब्दों में
इनपुट: दो बाइनरी ट्री की जड़ें, t1 और t2। मानो टी१, टी२ से बहुत बड़ा है (इंटरव्यू वाला आम ढाँचा)।
आउटपुट: अगर टी२, टी१ का सबट्री है तो true; वरना false।
परिभाषा: टी२, टी१ का सबट्री है अगर टी१ में कोई नोड n हो जिसकी जड़वाली शाखा टी२ से एकदम समान हो (मान और संरचना)।
उदाहरण
T1: 1
/ \
2 3
/ \ /
4 5 6
T2: 2
/ \
4 5
जवाब: true। टी१ की जड़ का बायाँ बच्चा टी२ से पूरा मिलता है।
T2': 2
/
4
जवाब: false अगर टी१ का नोड 2 अभी भी दायाँ बच्चा 5 रखता हो। सिर्फ आधी आकृति नहीं, पूरी संरचना चाहिए।
कोड से पहले स्पष्ट करो
- खाली टी२: अक्सर हर चीज़ का सबट्री माना जाता है (या ठुकरा दो; एक ठेका चुनो)। खाली टी१ और गैर-खाली टी२ =
false। - टी१ में मान दोहरा सकते हैं, इसलिए कई उम्मीदवार शुरूआतें हो सकती हैं।
- तुलना मान और संरचना से, ऑब्जेक्ट संदर्भ से नहीं (ट्री अक्सर अलग ऑब्जेक्ट होते हैं)।
- बाइनरी ट्री; ज़रूरी नहीं कि बीएसटी हो।
नोड का रूप
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
कोड से पहले सोचो
तरीका क: जड़ ढूँढो, फिर मैचट्री
१. टी१ घूमो (डीएफएस या बीएफएस)। जब नोड का val == t2.val हो, matchTree(node, t2) बुलाओ।
२. matchTree(a, b) तभी सत्य जब दोनों नल हों, या दोनों गैर-नल हों, एक ही मान हो, और बायाँ-दायाँ सबट्री भी मिलें।
३. कोई उम्मीदवार पूरा बैठे तो true। टी१ खत्म और कोई मेल नहीं तो false।
अधिकतर लोग पहले यही स्केच करते हैं। साफ है, अतिरिक्त स्ट्रिंग मेमोरी नहीं चाहिए।
सबसे खराब लागत: टी२ को टी१ के कई स्थानों पर मिला सकते हो। टी१ आकार एन, टी२ आकार एम, और टी२ की जड़ का मान कई जगह हो तो लगभग ओ(एन · एम) तक काम। मान कम दोहराए जाएँ तो ओ(एन + एम) के करीब।
तरीका ख: नल चिह्नों वाला प्रीऑर्डर, फिर कंटेन्स
१. टी१ और टी२ को प्रीऑर्डर से धाराबद्ध करो जो नल संतान लिखे (उदाहरण: नल के लिए X, या सीमांकक योजना)।
२. पूछो कि टी२ की स्ट्रिंग, टी१ की स्ट्रिंग की उपस्ट्रिंग है या नहीं।
नल चिह्न क्यों: बिना उन्हें अलग आकार एक जैसी स्ट्रिंग बन सकते हैं। उनके साथ, बड़े ट्री के प्रीऑर्डर का एक सटा हुआ टुकड़ा छोटे की पूरी धारा के बराबर हो तो जड़वाली आकृतियाँ मेल खाती हैं। मान जैसे 12 को 1 फिर 2 न समझा जाए, इसके लिए अलग करने वाले चिह्न भी चाहिए। आम पैटर्न: मान लपेटो "#3#", नल "#X#", जोड़ो, फिर contains।
समय: स्ट्रिंग बनाने में ओ(एन + एम) (अच्छी विधि से उपस्ट्रिंग खोज रैखिक; जावा का contains बताना ठीक)। जगह: स्ट्रिंगों के लिए ओ(एन + एम)।
इंटरव्यू आदत: आगे खोज + मैचट्री रखो। स्ट्रिंग तरीका दूसरा कोण: जगह देकर मिलान आसान।
जावा हल: खोज + मैचट्री
public class CheckSubtree {
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
/**
* Returns true if t2 is a subtree of t1 (same values and structure under some node).
* Empty t2 is treated as a subtree. Null t1 with non-empty t2 is not.
*/
public static boolean containsTree(TreeNode t1, TreeNode t2) {
if (t2 == null) {
return true;
}
if (t1 == null) {
return false;
}
return subTree(t1, t2);
}
/** Walk t1; at each node try a full match against t2. */
private static boolean subTree(TreeNode r1, TreeNode r2) {
if (r1 == null) {
return false;
}
if (r1.val == r2.val && matchTree(r1, r2)) {
return true;
}
return subTree(r1.left, r2) || subTree(r1.right, r2);
}
/** True only if both trees are identical from these roots. */
private static boolean matchTree(TreeNode a, TreeNode b) {
if (a == null && b == null) {
return true;
}
if (a == null || b == null) {
return false;
}
if (a.val != b.val) {
return false;
}
return matchTree(a.left, b.left) && matchTree(a.right, b.right);
}
}
पहले उदाहरण का ट्रेस: subTree टी१ घूमता है, नोड 2 पर पहुँचता है, matchTree 2/4/5 को टी२ से मिलाता है और true लौटाता है। काम खत्म।
अगर टी१ का 2 अलग दायाँ बच्चा रखता, matchTree फेल होता और खोज टी१ के बाकी हिस्से में चलती।
जावा हल: प्रीऑर्डर स्ट्रिंग + कंटेन्स
public class CheckSubtreeSerialized {
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
public static boolean containsTree(TreeNode t1, TreeNode t2) {
if (t2 == null) {
return true;
}
if (t1 == null) {
return false;
}
String s1 = serialize(t1);
String s2 = serialize(t2);
return s1.contains(s2);
}
/** Preorder with null markers and value wrappers so tokens cannot glue. */
private static String serialize(TreeNode node) {
StringBuilder sb = new StringBuilder();
write(node, sb);
return sb.toString();
}
private static void write(TreeNode node, StringBuilder sb) {
if (node == null) {
sb.append("#X#");
return;
}
sb.append('#').append(node.val).append('#');
write(node.left, sb);
write(node.right, sb);
}
}
उदाहरण का विचार (सरलीकृत टोकन): टी२ कुछ ऐसा #2##4##X##X##5##X##X#। true के लिए यह पूरा टुकड़ा टी१ की धारा के अंदर दिखना चाहिए। # लपेट 12 को 1 फिर 2 जैसा दिखने से रोकते हैं।
जटिलता
| तरीका | समय (लगभग) | अतिरिक्त जगह | नोट |
|---|---|---|---|
| खोज + मैचट्री | ओ(एन + के · एम) सबसे खराब ~ ओ(एन · एम) | ओ(एच) पुनरावृत्ति (टी१ / टी२ की ऊँचाई) | के = टी२ की जड़ का मान टी१ में कितनी बार |
| प्रीऑर्डर स्ट्रिंग + कंटेन्स | ओ(एन + एम) बनाना (+ रैखिक खोज) | ओ(एन + एम) स्ट्रिंग | मिलान आसान; मेमोरी चुकानी पड़ती है |
एन = टी१ के नोड, एम = टी२ के नोड। समस्या कहती है टी१ बहुत बड़ा है, दोनों व्यावहारिक; बताओ कौन सा समझौता चुनते हो।
किनारे के मामले जो इंटरव्यूअर छेड़ते हैं
१. नल / खाली टी२। ठेका: अक्सर true (खाली ट्री सबट्री है)। साफ बोलो।
२. नल टी१, गैर-खाली टी२। false।
३. एक जैसे ट्री। टी२ = टी१। पहला नोड पूरा बैठता है; true।
४. दोहराई जड़ मान। टी१ में टी२ की जड़ के बराबर कई नोड; सिर्फ एक पूरा मेल (या कोई नहीं)। पहला मान मिलते ही बिना matchTree मत रुकना।
५. वही मान, गलत आकार। बायाँ/दायाँ अदला-बदली, या नल गायब। matchTree और नल-चिह्नित धारा दोनों पकड़ते हैं।
६. टी२, टी१ से बड़ा। सिर्फ तब true जब आकार-संरचना समान; अक्सर false। दोनों एल्गोरिदम ठीक।
७. एक-नोड टी२। true तभी जब वह मान टी१ कहीं हो।
८. गहरे पतले ट्री। पुनरावृत्ति गहराई = ऊँचाई। स्टैक की बात करो; अगर पूछें तो इटरेटिव भी।
आम गलतियाँ
- सिर्फ जाँचना कि टी२ का हर मान टी१ में है (मल्टीसेट समानता)। आकार छूट जाता है।
- पूरा सबट्री की जगह सिर्फ रास्ता मिलाना (भाई शाखाएँ और नल भूलना)।
- बिना नल चिह्न धाराबद्ध करना, जिससे अलग टोपोलॉजी टकराएँ।
- मान सीमांकक के बिना धारा, जिससे बहु-अंक मान चिपकें (
12बनाम1,2)। subTreeमें मान मिलाकर बिना पूरी आकृति परmatchTreetrueलौटाना।- जाँच के दौरान टी१ या टी२ बदलना।
- "सबट्री" को "बीएसटी के अंदर टी२ रेंज" समझना। यह सामान्य बाइनरी ट्री और संरचनात्मक पहचान है।
दोस्त को बताने लायक सार
क्या छोटा ट्री बड़े के अंदर कहीं पूरी शाखा बनकर बैठा है?
बड़ा ट्री घूमो। छोटी जड़ का मान दिखे तो पूरी आकृति मिलाओ: दोनों नल, या एक ही मान और बायाँ-दायाँ एक जैसे। कोई उम्मीदवार बैठे तो हाँ।
या दोनों ट्री प्रीऑर्डर पाठ में लिखो जिसमें खाली संतान दर्ज हों और हर मान लिपटा हो। छोटा पाठ बड़े के अंदर हो तो आकृतियाँ मेल खाती हैं।
इंटरव्यू में खोज + मैचट्री आगे रखो। स्ट्रिंग वाला तरीका दूसरी कहानी जब दूसरा रास्ता माँगें।
अभ्यास
१. कागज़ पर याद से containsTree और matchTree लिखो।
२. टी१ बनाओ जिसमें टी२ की जड़ के बराबर दो नोड हों; सिर्फ एक सच्चा सबट्री। ट्रेस करो कौन सा उम्मीदवार फेल होता है।
३. छोटे ट्री को नल चिह्न के साथ और बिना धाराबद्ध करो; दिखाओ बिना चिह्न दो आकार कैसे टकराते हैं।
४. ओ(एन · एम) बनाम ओ(एन + एम) समझाओ और कब कौन दिखता है।
सीरीज़
- गाइड: सीटीसीआई सीरीज़ गाइड
- पिछला: बीएसटी सीक्वेंसेस
- अगला: रैंडम नोड