የሁለትዮሽ ፍለጋ ዛፍ Leetcode መፍትሄ ዝቅተኛው የጋራ ቅድመ አያት።

የችግር መግለጫ፡ የሁለትዮሽ ፍለጋ ዛፍ ዝቅተኛው የጋራ ቅድመ አያት ሌትኮድ መፍትሄ - ሁለትዮሽ የፍለጋ ዛፍ (BST) ከተሰጠው በBST ውስጥ ዝቅተኛውን የጋራ ቅድመ አያት (LCA) ኖድ ያግኙ። ማስታወሻ፡ “ዝቅተኛው የጋራ ቅድመ አያት በሁለት አንጓዎች p እና q መካከል በ T ውስጥ ያለው ዝቅተኛው መስቀለኛ መንገድ p እና q እንደ…

ተጨማሪ ያንብቡ

የደረጃ በደረጃ አቅጣጫዎች ከሁለትዮሽ ዛፍ መስቀለኛ መንገድ ወደ ሌላ የሊትኮድ መፍትሄ

የችግር መግለጫ፡- የደረጃ በደረጃ አቅጣጫዎች ከሁለትዮሽ ዛፍ መስቀለኛ መንገድ ወደ ሌላ የሊትኮድ መፍትሄ - የሁለትዮሽ ዛፍ ሥር ከ n ኖዶች ጋር ይሰጥዎታል። እያንዳንዱ መስቀለኛ መንገድ ከ 1 እስከ n ልዩ በሆነ ሁኔታ ይመደባል. እንዲሁም የመነሻ መስቀለኛ መንገዱን ዋጋ የሚወክል ኢንቲጀር ጅምር እሴት እና የመዳረሻውን ዋጋ የሚወክል የተለየ ኢንቲጀር ዴስትቫል ይሰጥዎታል…

ተጨማሪ ያንብቡ

የሁለትዮሽ ዛፍ LeetCode መፍትሄ አቀባዊ ቅደም ተከተል መሻገር

የችግር መግለጫ አቀባዊ ቅደም ተከተል የሁለትዮሽ ዛፍን መሻገር LeetCode መፍትሄ ይላል - የሁለትዮሽ ዛፍ ሥር ከተሰጠ ፣ የሁለትዮሽ ዛፍን ቀጥ ያለ ቅደም ተከተል አስላ። ለእያንዳንዱ መስቀለኛ መንገድ (ረድፍ ፣ ኮል) ፣ ግራ እና ቀኝ ልጆቹ በቦታዎች (ረድፍ + 1 ፣ ኮላ - 1) እና (ረድፍ + 1 ፣ ኮል + 1) በቅደም ተከተል ይሆናሉ። …

ተጨማሪ ያንብቡ

ድምር ስርወ ወደ ቅጠል ቁጥሮች LeetCode መፍትሄ

የችግር መግለጫ ድምር ስርወ ወደ ቅጠል ቁጥሮች LeetCode መፍትሄ እንዲህ ይላል - ከ 0 እስከ 9 አሃዞችን ብቻ የያዘ የሁለትዮሽ ዛፍ ስር ይሰጥዎታል። በዛፉ ውስጥ ያለው እያንዳንዱ ሥር-ወደ-ቅጠል መንገድ ቁጥርን ይወክላል. ለምሳሌ ከስር-ወደ-ቅጠል መንገድ 1 -> 2 -> 3 ቁጥርን ይወክላል 123. የሁሉም ስር-ወደ-ቅጠል ቁጥሮች ድምርን ይመልሱ። ሙከራ…

ተጨማሪ ያንብቡ

ሁለትዮሽ ዛፍ Inorder Traversal LeetCode መፍትሔ

የችግር መግለጫ፡- የሁለትዮሽ ዛፍ ቅደም ተከተል መሻገሪያ የሊትኮድ መፍትሄ የሁለትዮሽ ዛፍ ሥር ከተሰጠን፣ የአንጓዎቹን እሴቶቹን ቅደም ተከተል መተላለፍን ይመልሱ። ምሳሌ 1፡ ግብዓት፡ ስርወ = [1,null,2,3] ውጤት፡ [1,3,2፣2፣3] ምሳሌ 1፡ ግቤት፡ ስር = [] ውጤት፡ [] ምሳሌ 1፡ ግቤት፡ ስር = [XNUMX] ውጤት፡ [XNUMX] ገደቦች፡ በ ውስጥ ያሉት የአንጓዎች ብዛት…

ተጨማሪ ያንብቡ

ጠፍጣፋ ሁለትዮሽ ዛፍ ከተገናኘው ዝርዝር LeetCode መፍትሄ

ጠፍጣፋ ሁለትዮሽ ዛፍ ከተገናኘው ዝርዝር LeetCode መፍትሄ ይላል - የተሰጠው root የሁለትዮሽ ዛፍ ፣ ዛፉን ወደ “የተገናኘ ዝርዝር” ጠፍጣፋ ያድርጉት።

  • "የተገናኘው ዝርዝር" ተመሳሳይ መጠቀም አለበት TreeNode ክፍል የት right የህጻን ጠቋሚ በዝርዝሩ ውስጥ ወደሚቀጥለው መስቀለኛ መንገድ እና የ left የልጅ ጠቋሚ ሁልጊዜ ነው null.
  • "የተገናኘው ዝርዝር" በተመሳሳይ ቅደም ተከተል መሆን አለበት ሀ የቅድሚያ ትእዛዝ መተላለፍ የሁለትዮሽ ዛፍ.

 

ምሳሌ 1:

ጠፍጣፋ ሁለትዮሽ ዛፍ ከተገናኘው ዝርዝር LeetCode መፍትሄግቤት

 root = [1,2,5,3,4,null,6]

ውጤት

 [1,null,2,null,3,null,4,null,5,null,6]

ምሳሌ 2:

ግቤት

 root = []

ውጤት

 []

ምሳሌ 3:

ግቤት

 root = [0]

ውጤት

 [0]

 

አልጎሪዝም -

IDEA -

  • ሁለትዮሽ ዛፍን ለማንጠፍለቅ በመጀመሪያ የግራውን ንዑስ ዛፍ ትክክለኛውን አካል እናገኛለን እና ትክክለኛውን ንጥረ ነገር ካገኘን በኋላ የዚያን መስቀለኛ መንገድ የቀኝ ጠቋሚን ከተሰጠ የዛፍ ቀኝ ንዑስ ዛፍ ጋር እናገናኘዋለን።
  • ደረጃ 2 ላይ የስር መስቀለኛ መንገድ የቀኝ ጠቋሚን ከግራ-ንዑስ ዛፍ ጋር እናገናኘዋለን እና የግራ-ንዑስ ዛፍ ባዶ እናስቀምጣለን።
  • በደረጃ 3 ላይ አሁን የእኛ ስርወ ኖድ የቀኝ-ንዑስ መስቀለኛ መንገድ ነው ተመሳሳይ ሂደት በዚህ መስቀለኛ መንገድ ይከሰታል እና ሁሉም የግራ ክፍሎች ባዶ እስኪሆኑ ድረስ ሂደቱ ይቀጥላል።

የጠፍጣፋ ሁለትዮሽ ዛፍ ከተገናኘው ዝርዝር Leetcode መፍትሄ ጋር አቀራረብ -

- መጀመሪያ ላይ አንድ loop እሮጣለሁ (ሥር ! = null) ከዚያ ሁለት ተለዋዋጮችን ወስጄ የግራ-ንዑስ ዛፍን አከማችታለሁ።

- ከዚያም (k.left != null) በመጠቀም በቀኝ በኩል ያለውን የግራ-ንዑስ ዛፍ ኖድ ይፈትሹ እና ያንን መስቀለኛ መንገድ ከቀኝ ንዑስ ዛፍ ጋር ያገናኘዋል (k.right = root.right)።

- በመቀጠል የቀኝ ጠቋሚውን የስር ኖድ በግራ ንዑስ ዛፍ (root.right = ግራ) ያገናኙ እና የግራ ጠቋሚውን ባዶ (root.left=null) አድርገው ያስቀምጡ እና በ ( root = root.right ) ይሻሻላል ስለዚህ አሁን ስርወ ትክክል ነው የከርሰ ምድር መስቀለኛ መንገድ.

- ሁሉም የግራ-ንዑስ ክፍሎች ትክክለኛ ንዑስ ክፍል እስኪሆኑ ድረስ ይህ ሂደት ይቀጥላል። ስለዚህ, የሁለትዮሽ ዛፉ ጠፍጣፋ ይሆናል.

 

ጠፍጣፋ ሁለትዮሽ ዛፍ ከተገናኘው ዝርዝር LeetCode መፍትሄ

ጠፍጣፋ ሁለትዮሽ ዛፍ ከተገናኘው ዝርዝር LeetCode መፍትሄ

Python መፍትሄ፡-

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        while(root):
            
            if root.left:
                
                k = root.left
                temp = root.left
            
            
                while(k.right):
                    k = k.right
            
                k.right = root.right
            
                root.right = temp
            
                root.left = None
            
            root = root.right

የጃቫ መፍትሄ፡-

class Solution {
    public void flatten(TreeNode root) {       
        while (root != null) {
            if (root.left != null) {
                TreeNode k = root.left;
                TreeNode temp = root.left;
                while (k.right != null) k = k.right;
                k.right = root.right;
                root.right = temp;
                root.left = null;
            }
            root = root.right;
        }
    }
}

የጊዜ ውስብስብነት፡ O(N)

የቦታ ውስብስብነት: - O (1)

አንድ ጊዜ ብቻ እንደተጓዝን፣ የጊዜ ውስብስብነት o(n) ይሆናል።

እና ምንም ተጨማሪ ቦታ ስላልወሰድን የቦታ ውስብስብነት o(1) የማያቋርጥ ተጨማሪ ቦታ ይሆናል።

ተመሳሳይ ጥያቄ- https://www.tutorialcup.com/interview/linked-list/flattening-linked-list.htm

የ N-Ary Tree LeetCode መፍትሄ ዲያሜትር

የችግር መግለጫ የ N-Ary Tree LeetCode መፍትሄ ዲያሜትር - የ N-ary ዛፍ ሥር ከተሰጠው በኋላ የዛፉን ዲያሜትር ርዝመት ማስላት ያስፈልግዎታል. የ N-ary ዛፍ ዲያሜትር በዛፉ ውስጥ ባሉ ሁለት አንጓዎች መካከል ያለው ረጅሙ መንገድ ርዝመት ነው። ይህ መንገድ ሊሆንም ላይሆንም ይችላል…

ተጨማሪ ያንብቡ

የሁለትዮሽ ዛፍ Leetcode መፍትሄ ዝቅተኛው የጋራ ቅድመ አያት።

የችግር መግለጫ የሁለትዮሽ ዛፍ ሌትኮድ መፍትሄ ዝቅተኛው የጋራ ቅድመ አያት - "የሁለትዮሽ ዛፍ ዝቅተኛው የጋራ ቅድመ አያት" የሚለው የሁለትዮሽ ዛፍ ሥር እና የዛፉን ሁለት አንጓዎች እንደሰጠ ይናገራል። የእነዚህ ሁለት አንጓዎች ዝቅተኛውን የጋራ ቅድመ አያት ማግኘት አለብን. በጣም ዝቅተኛው የጋራ…

ተጨማሪ ያንብቡ

በእያንዳንዱ መስቀለኛ መንገድ Leetcode መፍትሄ ቀጣይ የቀኝ ጠቋሚዎችን ማብዛት።

የችግር መግለጫ በእያንዳንዱ መስቀለኛ መንገድ ላይ ያለው ቀጣይ የቀኝ ጠቋሚዎች ሊትኮድ መፍትሄ - "በእያንዳንዱ መስቀለኛ መንገድ ቀጣይ የቀኝ ጠቋሚዎችን ማብዛት" የሚለው የፍፁም የሁለትዮሽ ዛፍ ስር እንደ ሆነ እና እያንዳንዱን ቀጣይ የመስቀለኛ መንገድ ጠቋሚ ወደ ቀጣዩ የቀኝ መስቀለኛ መንገድ መሙላት አለብን። ቀጣይ ከሌለ…

ተጨማሪ ያንብቡ

አንጓዎችን ሰርዝ እና የደን Leetcode መፍትሄን ተመለስ

የችግሮች መግለጫ መስቀለኛ መንገዶችን ሰርዝ እና የደን መመለሻ LeetCode መፍትሄ - "ኖዶችን ሰርዝ እና ደን መመለስ" የሚለው እያንዳንዱ መስቀለኛ መንገድ የተለየ ዋጋ ያለው የሁለትዮሽ ዛፍ ሥር ይሰጣል። እንዲሁም ሁሉንም ዋጋ ያላቸውን አንጓዎች መሰረዝ የሚያስፈልገንን ድርድር_ለመሰረዝ ተሰጥቶናል።

ተጨማሪ ያንብቡ

Translate »