Քայլ առ քայլ ուղղություններ Երկուական ծառի հանգույցից մինչև մեկ այլ LeetCode լուծում

Խնդրի հայտարարություն. քայլ առ քայլ ուղղություններ երկուական ծառի հանգույցից մինչև մեկ այլ LeetCode լուծում – Ձեզ տրվում է n հանգույց ունեցող երկուական ծառի արմատը: Յուրաքանչյուր հանգույցին եզակիորեն վերագրվում է 1-ից n արժեք: Ձեզ տրվում է նաև սկզբնական արժեքի ամբողջ թիվ, որը ներկայացնում է սկզբնական հանգույցի արժեքը, և մեկ այլ ամբողջ թիվ destValue, որը ներկայացնում է նպատակակետի արժեքը…

Կարդալ ավելին

Երկուական ծառի LeetCode լուծույթի ուղղահայաց կարգի անցում

Խնդրի հայտարարություն Երկուական ծառի ուղղահայաց կարգի անցում LeetCode Solution-ը ասում է. Հաշվի առնելով երկուական ծառի արմատը, հաշվարկեք երկուական ծառի ուղղահայաց կարգի անցումը: Դիրքում գտնվող յուրաքանչյուր հանգույցի համար (տող, սյունակ), նրա ձախ և աջ երեխաները համապատասխանաբար կլինեն դիրքերում (տող + 1, սյուն – 1) և (տող + 1, սյուն + 1) դիրքերում: …

Կարդալ ավելին

Գումարի արմատից տերևի համարներ LeetCode լուծում

Խնդրի ձևակերպում Գումար Արմատից մինչև տերևային թվեր LeetCode Solution-ը ասում է. Ձեզ տրվում է միայն 0-ից 9 թվանշաններ պարունակող երկուական ծառի արմատը: Ծառի յուրաքանչյուր արմատից տերև ճանապարհը ներկայացնում է մի թիվ: Օրինակ, արմատից տերեւ ուղին 1 -> 2 -> 3 ներկայացնում է 123 թիվը: Վերադարձրեք արմատից տերեւ բոլոր թվերի ընդհանուր գումարը: Փորձարկում …

Կարդալ ավելին

Binary Tree Inorder Traversal LeetCode լուծում

Խնդրի ձևակերպում. Երկուական ծառի կարգի անցում LeetCode լուծում Հաշվի առնելով երկուական ծառի արմատը, վերադարձրեք նրա հանգույցների արժեքների հերթականության անցումը: Օրինակ 1. Մուտք. արմատ = [1,null,2,3] Ելք՝ [1,3,2] Օրինակ 2. Մուտք՝ արմատ = [] Ելք՝ [] Օրինակ 3. Մուտք՝ արմատ = [1] Ելք: [1] Սահմանափակումներ. հանգույցների թիվը…

Կարդալ ավելին

Հարթեցրեք Երկուական ծառը կապակցված ցուցակին LeetCode լուծում

Հարթեցրեք Երկուական ծառը կապակցված ցուցակին LeetCode լուծում ասում է, որ – Հաշվի առնելով root երկուական ծառից, ծառը հարթեցրեք «կապված ցուցակի» մեջ.

  • «Կապված ցուցակը» պետք է օգտագործի նույնը TreeNode դասարան, որտեղ right երեխայի ցուցիչը ցույց է տալիս ցուցակի հաջորդ հանգույցը և left երեխայի ցուցիչը միշտ է null.
  • «Կապված ցուցակը» պետք է լինի նույն հաջորդականությամբ, ինչ a նախնական պատվեր անցում երկուական ծառից:

 

Օրինակ 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]

 

ԱԼԳՈՐԻԹՄ –

ԳԱՂԱՓԱՐ –

  • Երկուական ծառը հարթեցնելու համար նախ կգտնենք ձախ ենթածառի ամենաաջ տարրը և ամենաաջ տարրը ստանալուց հետո այդ հանգույցի աջ ցուցիչը կկապենք տվյալ ծառի աջ ենթածառի հետ:
  • 2-րդ քայլում մենք արմատային հանգույցի աջ ցուցիչը կկապենք ձախ ենթածառի հետ և ձախ ենթածառը կսահմանենք որպես զրոյական:
  • Քայլ 3-ում այժմ մեր արմատային հանգույցը աջ ենթածառի հանգույց է, նույն գործընթացը տեղի կունենա այս հանգույցի հետ և գործընթացը դեռ կշարունակվի այնքան ժամանակ, մինչև բոլոր ձախ մասերը զրոյանան:

Երկուական ծառի հարթեցման մոտեցում Leetcode լուծման հետ կապված ցուցակին –

– Սկզբում ես կգործարկեմ հանգույց, այսինքն՝ while(root != null), այնուհետև կվերցնեմ երկու փոփոխական և կպահեմ ձախ ենթածառը:

– այնուհետև ստուգելու է ձախ ենթածառի ամենաաջ հանգույցը՝ օգտագործելով while(k.left != null) և այդ հանգույցը կապելու է աջ ենթածառի հետ՝ օգտագործելով (k.right = root.right):

– այնուհետև կապեք արմատային հանգույցի աջ ցուցիչը ձախ ենթածառի հետ (root.right = ձախ) և սահմանեք արմատային հանգույցի ձախ ցուցիչը որպես null(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

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

Ժամանակի բարդություն՝ O(N)

Տիեզերական բարդություն. O (1)

Քանի որ մենք անցել ենք միայն մեկ անգամ, ժամանակի բարդությունը կլինի o(n):

և քանի որ մենք որևէ լրացուցիչ տարածություն չենք վերցրել, տիեզերական բարդությունը կլինի o(1) մշտական ​​լրացուցիչ տարածություն:

Նմանատիպ հարց - https://www.tutorialcup.com/interview/linked-list/flattening-linked-list.htm

N-Ary Tree LeetCode լուծույթի տրամագիծը

Խնդրի ձևակերպում. N-արյան ծառի տրամագիծը LeetCode լուծում – Հաշվի առնելով N-արյան ծառի արմատը, դուք պետք է հաշվարկեք ծառի տրամագծի երկարությունը: N-արյան ծառի տրամագիծը ծառի ցանկացած երկու հանգույցների միջև ամենաերկար ճանապարհի երկարությունն է: Այս ճանապարհը կարող է կամ ոչ…

Կարդալ ավելին

Երկուական ծառի Leetcode լուծույթի ամենացածր ընդհանուր նախնին

Խնդրի հայտարարություն Երկուական ծառի ամենացածր ընդհանուր նախահայրը LeetCode լուծում – «Երկուական ծառի ամենացածր ընդհանուր նախահայրը» նշում է, որ հաշվի առնելով երկուական ծառի արմատը և ծառի երկու հանգույցները: Մենք պետք է գտնենք այս երկու հանգույցների ամենացածր ընդհանուր նախնին: Ամենացածր ընդհանուր…

Կարդալ ավելին

Հաջորդ աջ ցուցիչների համալրում յուրաքանչյուր հանգույցի Leetcode լուծումում

Խնդրի ձևակերպում Հաջորդ աջ ցուցիչները յուրաքանչյուր հանգույցում բնակեցնելով LeetCode լուծում – «Հաջորդ աջ ցուցիչների համալրում յուրաքանչյուր հանգույցում» նշում է, որ հաշվի առնելով կատարյալ երկուական ծառի արմատը, և մենք պետք է լրացնենք հանգույցի յուրաքանչյուր հաջորդ ցուցիչը իր հաջորդ աջ հանգույցում: Եթե ​​չկա հաջորդ…

Կարդալ ավելին

Ջնջել հանգույցները և վերադարձնել Forest Leetcode լուծումը

Խնդրի հայտարարություն Ջնջել հանգույցները և վերադարձնել անտառը LeetCode լուծում – «Ջնջել հանգույցները և վերադարձնել անտառը» նշում է, որ հաշվի առնելով երկուական ծառի արմատը, որտեղ յուրաքանչյուր հանգույց ունի որոշակի արժեք: Մեզ տրվում է նաև զանգված՝ to_delete, որտեղ մենք պետք է ջնջենք բոլոր այն հանգույցները, որոնց արժեքները պարունակվում են…

Կարդալ ավելին

Վերականգնել Երկուական որոնման ծառի Leetcode լուծումը

Խնդրի հայտարարություն Վերականգնել երկուական որոնման ծառը LeetCode լուծում – «Վերականգնել երկուական որոնման ծառը» նշում է, որ հաշվի առնելով երկուական որոնման ծառի արմատը, որտեղ սխալմամբ փոխվում են ուղիղ երկու հանգույցների արժեքները: Մենք պետք է վերականգնենք ծառը՝ առանց նրա կառուցվածքը փոխելու։ Օրինակ՝ Մուտք՝ արմատ = [1,3,null,null,2] Ելք՝ [3,1,null,null,2] …

Կարդալ ավելին

Translate »