Traversazzjoni tal-Ordni Vertikali tas-Soluzzjoni LeetCode tas-Siġra Binarja

Dikjarazzjoni tal-Problema Traversazzjoni tal-Ordni Vertikali tas-Siġra Binarja Soluzzjoni LeetCode tgħid - Minħabba l-għerq ta 'siġra binarja, ikkalkula t-traversal tal-ordni vertikali tas-siġra binarja. Għal kull node fil-pożizzjoni (ringiela, kol), it-tfal tax-xellug u tal-lemin tiegħu jkunu f'pożizzjonijiet (ringiela + 1, kol – 1) u (ringiela + 1, kol + 1) rispettivament. …

Aqra iktar

Somm Għerq għal Numri tal-Ferqa Soluzzjoni LeetCode

Dikjarazzjoni tal-Problema Sum Root to Leaf Numbers Soluzzjoni LeetCode tgħid – Inti tingħata l-għerq ta 'siġra binarja li fiha ċifri minn 0 sa 9 biss. Kull mogħdija mill-għeruq għall-weraq fis-siġra tirrappreżenta numru. Pereżempju, il-mogħdija mill-għeruq għall-weraq 1 -> 2 -> 3 tirrappreżenta n-numru 123. Irritorna s-somma totali tan-numri kollha mill-għeruq għall-weraq. Test...

Aqra iktar

Binary Tree Inorder Traversal Soluzzjoni LeetCode

Dikjarazzjoni tal-Problema: Binary Tree Inorder Traversal Soluzzjoni LeetCode Minħabba l-għerq ta 'siġra binarja, ritorna l-inorder traversal tal-valuri tan-nodi tagħha. Eżempju 1: Input: root = [1,null,2,3] Output: [1,3,2] Eżempju 2: Input: root = [] Output: [] Eżempju 3: Input: root = [1] Output: [1] Limitazzjonijiet: In-numru ta' nodi fi...

Aqra iktar

Huwa Graph Bipartite? Soluzzjoni LeetCode

Dikjarazzjoni tal-Problema Huwa Graph Bipartite LeetCode Soluzzjoni - Hemm graff mhux dirett b'n nodi, fejn kull nodu huwa nnumerat bejn 0 u n - 1. Int tingħata graff ta 'array 2D, fejn graph[u] hija firxa ta' nodi li n-nodu u hija biswit. B'mod aktar formali, għal kull v fil-graff[u], hemm tarf mhux dirett bejn in-node u u n-nodu v. Il-graff għandu...

Aqra iktar

Disinn Żid u Fittex Kliem Struttura tad-Dejta Soluzzjoni LeetCode

Dikjarazzjoni tal-Problema: Disinn Żid u Fittex Kliem Struttura tad-Dejta Soluzzjoni LeetCode jgħid – Iddisinja struttura tad-dejta li tappoġġja ż-żieda ta 'kliem ġdid u s-sejba jekk string taqbilx ma' xi string miżjuda qabel. Implimenta l-klassi WordDictionary: WordDictionary() Inizjalizza l-oġġett. void addWord(word) Iżżid kelma mal-istruttura tad-dejta, tista' titqabbel aktar tard. bool search(word) Jirritorna vera jekk hemm...

Aqra iktar

Flatten Binary Tree to Linked List Soluzzjoni LeetCode

Flatten Binary Tree to Linked List Soluzzjoni LeetCode jgħid li – Minħabba l- root ta’ siġra binarja, iċċattja s-siġra f’“lista marbuta”:

  • Il-“lista marbuta” għandha tuża l-istess TreeNode klassi fejn il right il-punter tat-tifel jindika n-nodu li jmiss fil-lista u l- left punter tat-tfal huwa dejjem null.
  • Il-“lista konnessa” għandha tkun fl-istess ordni bħal a qabel l-ordni traversal tas-siġra binarja.

 

Eżempju 1:

Flatten Binary Tree to Linked List Soluzzjoni LeetCodeinput:

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

Riżultat:

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

Eżempju 2:

input:

 root = []

Riżultat:

 []

Eżempju 3:

input:

 root = [0]

Riżultat:

 [0]

 

ALGORITMU -

IDEA -

  • Sabiex iċċattjaw siġra binarja, l-ewwel se nsibu l-element l-aktar tal-lemin tas-subsiġra tax-xellug u wara li ksibna l-element l-aktar tal-lemin aħna se torbot il-punter tal-lemin ta 'dak in-node ma' subtree tal-lemin ta 'siġra partikolari.
  • Fil-pass 2 aħna se torbot il-pointer tal-lemin tan-nodu għerq mas-subtree tax-xellug u nissettjaw is-subtree tax-xellug bħala null.
  • Fil-pass 3 issa node għerq tagħna huwa node subtree dritt istess proċess se jiġri ma 'dan in-node u l-proċess xorta se jkompli sakemm il-partijiet tax-xellug kollha jsiru nulli.

Approċċ għal Flatten Binary Tree to Linked List Soluzzjoni Leetcode -

– Għall-ewwel, i se tmexxi loop jiġifieri filwaqt (għerq != null) imbagħad se tieħu żewġ varjabbli u jaħżen is-subtree tax-xellug.

– imbagħad se tiċċekkja għan-node l-aktar tal-lemin tas-subtree tax-xellug billi tuża while(k.left != null) u se torbot dak in-node mas-subtree tal-lemin billi tuża (k.right = root.right).

– imbagħad għaqqad il-pointer tal-lemin tan-node tal-għeruq ma’ subtree tax-xellug (għerq.right = xellug) u ssettja l-pointer tax-xellug tan-nodu tal-għerq bħala null(għerq.xellug=null) u se taġġorna minn (għerq = għerq.lemin) għalhekk issa l-għerq huwa dritt subtree node.

– dan il-proċess se jkompli sakemm il-partijiet kollha tas-subtree tax-xellug isiru subtree tal-lemin. Għalhekk, is-siġra binarja se tiċċattja.

 

Flatten Binary Tree to Linked List Soluzzjoni LeetCode

Flatten Binary Tree to Linked List Soluzzjoni LeetCode

Soluzzjoni 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

Soluzzjoni Java:

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;
        }
    }
}

Il-kumplessità tal-ħin: O(N)

Kumplessità Spazjali: O (1)

Peress li għaddejna darba biss, il-kumplessità tal-ħin se tkun o(n).

u peress li aħna ma ħadu ebda spazju żejjed, il-kumplessità tal-ispazju se tkun o(1) spazju żejjed kostanti.

Mistoqsija Simili - https://www.tutorialcup.com/interview/linked-list/flattening-linked-list.htm

L-Arħas Antenat Komuni ta’ Soluzzjoni Leetcode tas-Siġra Binarja

Dikjarazzjoni tal-Problema L-Inqas Antenat Komuni ta 'Siġra Binarja Soluzzjoni LeetCode - "L-aktar Antenat Komuni ta' Siġra Binarja" jiddikjara li minħabba l-għerq tas-siġra binarja u żewġ nodi tas-siġra. Għandna bżonn insibu l-aktar antenat komuni baxx ta 'dawn iż-żewġ nodi. L-iktar baxx komuni...

Aqra iktar

Populazzjoni ta' Pointers Dritt Li Jmiss f'Kull Soluzzjoni Leetcode Node

Dikjarazzjoni tal-problema Il-Populating Next Right Pointers f'kull Node Soluzzjoni LeetCode - "Populating Next Right Pointers f'kull Node" jiddikjara li minħabba l-għerq tas-siġra binarja perfetta u għandna bżonn timla kull pointer li jmiss tan-node għan-nodu dritt li jmiss tiegħu. Jekk ma jkunx hemm li jmiss...

Aqra iktar

Translate »