פלאַטאַן ביינערי טרי צו לינגקט רשימה LeetCode לייזונג זאגט אַז - געגעבן די root פון אַ ביינערי בוים, פלאַטאַן דעם בוים אין אַ "לינגקט רשימה":

• די "לינגקט רשימה" זאָל נוצן די זעלבע TreeNode קלאַס ווו די right קינד טייַטל ווייזט צו די ווייַטער נאָדע אין דער רשימה און די left קינד טייַטל איז שטענדיק null.
• די "לינגקט רשימה" זאָל זיין אין דער זעלביקער סדר ווי אַ פאַר - סדר דורכפאָר פון די ביינערי בוים.

 

לעמאָשל קסנומקס:

ינפּוט:

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

אָוטפּוט:

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

לעמאָשל קסנומקס:

ינפּוט:

 root = []

אָוטפּוט:

 []

לעמאָשל קסנומקס:

ינפּוט:

 root = [0]

אָוטפּוט:

 [0]

 

אַלגערידאַם -

IDEA -

• אין סדר צו פלאַטאַן אַ ביינערי בוים, מיר וועלן ערשטער געפֿינען די רעכט-מאָסט עלעמענט פון די לינקס סובטריע און נאָך מיר האָבן די רעכט-מאָסט עלעמענט, מיר וועלן פֿאַרבינדן די רעכט טייַטל פון אַז נאָדע מיט אַ רעכט סובטריע פון ​​אַ געגעבן בוים.
• אין שריט 2 מיר וועלן פֿאַרבינדן די רעכט טייַטל פון די וואָרצל נאָדע מיט די לינקס-סובטרי און שטעלן די לינקס-סובטרי ווי נאַל.
• אין שריט 3 איצט אונדזער וואָרצל נאָדע איז אַ רעכט-סובטרי נאָדע דער זעלביקער פּראָצעס וועט פּאַסירן מיט דעם נאָדע און דער פּראָצעס וועט נאָך פאָרזעצן ביז אַלע די לינקס פּאַרץ ווערן נאַל.

צוגאַנג פֿאַר פלאַטאַן ביינערי טרי צו לינגקט רשימה Leetcode לייזונג -

- אין ערשטער, איך וועט לויפן אַ שלייף, הייסט בשעת (וואָרצל != null) און וועט נעמען צוויי וועריאַבאַלז און קראָם די לינקס-סובטרי.

- דערנאָך וועט טשעק טשעק פֿאַר די רעכט נאָדע פון ​​לינקס-סובטרי דורך ניצן while (k.left != null) און וועט פֿאַרבינדן דעם נאָדע מיט רעכט סובטריע ניצן (ק.right = root.right).

- דעמאָלט לינק רעכט טייַטל פון וואָרצל נאָדע מיט לינקס סובטריע (root.right = לינקס) און שטעלן די לינקס טייַטל פון וואָרצל נאָדע ווי null (root.left = null) און וועט דערהייַנטיקן דורך ( וואָרצל = root.right ) אַזוי איצט וואָרצל איז רעכט סובטריע נאָדע.

- דער פּראָצעס וועט פאָרזעצן ביז אַלע לינקס-סובטרי פּאַרץ ווערן רעכט סובטריע. דעריבער, די ביינערי בוים וועט באַקומען פלאַטאַנד.

 

פּיטהאָן לייזונג:

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 לייזונג:

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

צייט קאַמפּלעקסיטי: אָ(ען)

אָרט קאַמפּלעקסיטי: אָ (1)

ווי מיר האָבן דורכגעגאנגען בלויז אַמאָל, צייַט קאַמפּלעקסיטי וועט זיין o (n).

און ווי מיר האָבן נישט גענומען קיין עקסטרע פּלאַץ, פּלאַץ קאַמפּלעקסיטי וועט זיין אָ (1) קעסיידערדיק עקסטרע פּלאַץ.

ענליכע פראגע - https://www.tutorialcup.com/interview/linked-list/flattening-linked-list.htm