બાઈનરી ટ્રીની બાઉન્ડ્રી ટ્રાવેસલ - ટ્યુટોરિયલકઅપ
મુખ્ય પૃષ્ઠ » તકનીકી ઇન્ટરવ્યૂ પ્રશ્નો » વૃક્ષ ઇન્ટરવ્યુ પ્રશ્નો » બાઈનરી ટ્રીની બાઉન્ડ્રી ટ્રાવર્સલ
વારંવાર પૂછવામાં આવે છે ભેગા એમેઝોન પર્યટન કૃતિકાલ ઉકેલો માઈક્રોસોફ્ટ મોર્ગન સ્ટેન્લી પે સ્નેપડીલ
બાઈનરી ટ્રીની બાઉન્ડ્રી ટ્રાવેર્સલ છાપવા માટે સી ++ કોડ
બાઈનરી ટ્રીની બાઉન્ડ્રી ટ્રાવેર્સલ છાપવા માટે જાવા કોડ
"બાઈનરી ટ્રીની બાઉન્ડ્રી ટ્રાવર્સલ" સમસ્યા જણાવે છે કે તમને બાઈનરી ટ્રી આપવામાં આવે છે. હવે તમારે a નું બાઉન્ડ્રી વ્યૂ છાપવાની જરૂર છે દ્વિસંગી વૃક્ષ. અહીં બાઉન્ડ્રી ટ્રાવર્સલ એટલે કે બધા ગાંઠો ઝાડની સીમા તરીકે બતાવવામાં આવે છે. ગાંઠો ઉપરની બાજુથી, ડાબી બાજુથી, નીચેની બાજુથી અને જમણી બાજુથી, ઘડિયાળની વિરુદ્ધ દિશામાં દેખાય છે. પરંતુ જો આપણે આ બધા દૃશ્યો સીધા જ છાપ્યા હોત, તો તેના પરિણામ રૂપે તે જ ગાંઠો ઘણી વખત છાપવામાં આવશે. તેથી બાઉન્ડ્રી વ્યુ છાપો જેમ કે ગાંઠો પુનરાવર્તિત ન થાય.
અહીં, બધા ગાંઠો બાઉન્ડ્રી નોડ્સ છે. પરંતુ આપણે ગાંઠો વિરોધી દિશામાં છાપવાની જરૂર છે. આમ આપણે 2 ની મૂળથી શરૂ કરીએ છીએ. પછી, આપણે ફક્ત તે જ રીતે આગળ વધીએ છીએ અને ગાંઠો 2, 3, 4, 6, 4, 7 છાપીશું.
સમસ્યા અમને ઝાડની બાઉન્ડ્રી છાપવા માટે કહે છે, અહીં આપણે ડાબી, જમણી અને નીચેની સીમા રાખી છે. જો ઝાડની કોઈ ડાબી અથવા જમણી સીમા નથી. રુટ પોતે ડાબી અથવા જમણી સીમા તરીકે માનવામાં આવે છે. આમાં એક શરત પણ છે કે જો આપણે બાઉન્ડ્રી નોડ્સ છાપીએ, તો આપણે કાળજી લેવાની જરૂર છે કે બે ગાંઠોમાંથી કોઈ પણ ઘણી વખત છાપવામાં ન આવે.
સમસ્યા હલ કરવા માટે, અમે ઝાડની ડાબી સીમાથી પ્રારંભ કરીશું. આપણે કહી શકીએ કે જો નોડ ડાબી બાજુથી દેખાય તો તે નોડ ડાબી સીમાની છે. એ જ રીતે, અમે જમણી બાજુના ગાંઠો અને પાંદડા ગાંઠો વ્યાખ્યાયિત કરીએ છીએ. ડાબી સીમા છાપવા માટે, અમે ઝાડને એવી રીતે પસાર કરીશું કે જો મૂળમાં ડાબી બાજુ નોડ હોય તો, પછી તેના જમણા નોડ પર ખસેડો. એકવાર આપણે પર્ણ નોડ પર પહોંચીશું. અમે પર્ણ ગાંઠોને છાપતા નથી કારણ કે આપણે વારંવાર પર્ણ ગાંઠો અલગથી છાપીએ છીએ. એકવાર આપણે ડાબી બાઉન્ડ્રી સાથે થઈ ગયાં.
આપણે લીફ ગાંઠો છાપીએ છીએ, પ્રથમ વારંવાર ડાબી સબટ્રી પાંદડા છાપવા દ્વારા. ડાબી સબટ્રી પાંદડા છાપ્યા પછી જમણા સબટ્રીમાં પાંદડા છાપો. આ રીતે બધા પાંદડા ગાંઠો વિરોધી ઘડિયાળની દિશામાં છાપવામાં આવશે. એકવાર અમે પાંદડા છાપીશું, પછી આપણે જમણી સીમાના ગાંઠો છાપીશું. આ સમયે ગાંઠોને નીચે-નીચેની રીતે છાપવાની જરૂર છે. આમ અંદર રિકર્ઝન, પહેલા આપણે ઝાડની ડાબી અથવા જમણી સબટ્રી હલ કરીએ અને પછી વર્તમાન નોડને પીક્રોપ્રિન્ટ કરીએ.
ઓ (એન), કારણ કે આપણે ઝાડના બધા ગાંઠોમાંથી પસાર થઈ ગયા છે. જ્યારે આપણે પ્રિંટલેફ્ટ, પ્રિન્ટરાઇટ અને પ્રિંટલેવ ફંક્શનનો ઉપયોગ કરીએ છીએ ત્યારે અમે ગાંઠોમાંથી પસાર થઈએ છીએ. આમ સમય જટિલતા રેખીય છે.
ઓ (એચ), જ્યાં H એ ઝાડની heightંચાઈ છે. આ કારણ છે કે કમ્પાઇલર સ્ટેક જગ્યાનો ઉપયોગ કરે છે. અને સીમા તત્વોને છાપવા માટે ઉપયોગમાં લેવામાં આવતા કાર્યો રિકર્ઝનનો ઉપયોગ કરે છે જે કમ્પાઇલર સ્ટેકની ગણતરી કરે છે.
શ્રેણીઓ વૃક્ષ ઇન્ટરવ્યુ પ્રશ્નો ટૅગ્સ ભેગા, એમેઝોન, દ્વિસંગી વૃક્ષ, પર્યટન, કૃતિકાલ ઉકેલો, મધ્યમ, માઈક્રોસોફ્ટ, મોર્ગન સ્ટેન્લી, પે, સ્નેપડીલ, વૃક્ષ, વૃક્ષ આડેધડ પોસ્ટ સંશોધક