Atsipazo ny hazo binary mankany amin'ny Lisitra mifandray LeetCode Solution milaza fa – Nomena ny root amin'ny hazo mimari-droa, tapaho ny hazo ho "lisitra mifandray":

• Ny "lisitra mifandray" dia tokony hampiasa mitovy TreeNode kilasy misy ny right manondro ny node manaraka ao amin'ny lisitra sy ny left ankizy pointer dia foana null.
• Ny "lisitra mifandray" dia tokony hitovy filaharana amin'ny a kaomandy mialoha mpandeha an-tongotra ny hazo binary.

 

Ohatra 1:

fahan'ny:

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

Fivoahana:

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

Ohatra 2:

fahan'ny:

 root = []

Fivoahana:

 []

Ohatra 3:

fahan'ny:

 root = [0]

Fivoahana:

 [0]

 

ALGORITMA –

IDE -

• Mba hametahana hazo mimari-droa, dia ho hitantsika aloha ny singa havanana indrindra amin'ny zana-kazo havia ary rehefa avy nahazo ny singa havanana isika dia hampifandray ny tondro havanana amin'io node io miaraka amin'ny zana-kazo havanana amin'ny hazo iray.
• Amin'ny dingana 2 dia hampifandray ny tondro havanana amin'ny fototry ny fotony amin'ny zana-kazo havia isika ary hametraka ny zana-kazo havia ho null.
• Ao amin'ny dingana 3 izao ny fototry ny fotony dia zana-trondro havanana ny dingana mitovy amin'ity node ity ary mbola hitohy ny dingana mandra-pahatongan'ny faritra havia rehetra ho tsy misy dikany.

Fomba fiasa ho an'ny hazo binary flatten amin'ny vahaolana mifandraika amin'ny Leetcode -

– Amin'ny voalohany dia hanao loop aho izany hoe while(root != null) avy eo haka variables roa ary hitahiry ny subtree havia.

– avy eo dia hanamarina ny node farany havanana amin'ny havia-subtree amin'ny fampiasana while(k.left != null) ary hampifandray an'io node io amin'ny zana-kazo havanana amin'ny fampiasana (k.right = root.right).

– avy eo ampifandraiso amin'ny zana-kazo havia (root.right = ankavia) ny tondro havanana amin'ny node fakany ary apetraho ho null(root.left=null) ny tondro havia amin'ny root. zana-kazo node.

– hitohy ity dingana ity mandra-pahatongan'ny tapany havia rehetra ho zana-kazo havanana. Noho izany, ny hazo binary dia ho lany.

 

Vahaolana 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

Java Solution:

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

Sarotra ny fotoana: O(N)

Fahasarotana amin'ny habakabaka: O (1)

Satria indray mandeha ihany no nandalovanay dia ho o(n) ny fahasarotan'ny fotoana.

ary satria tsy naka toerana fanampiny izahay, ny fahasarotan'ny habaka dia ho (1) habaka fanampiny tsy tapaka.

Fanontaniana mitovy - https://www.tutorialcup.com/interview/linked-list/flattening-linked-list.htm