Пакрокавыя інструкцыі ад вузла бінарнага дрэва да іншага рашэння LeetCode

Пастаноўка праблемы: Пакрокавыя інструкцыі ад вузла двайковага дрэва да іншага рашэння LeetCode – Вам дадзены корань двайковага дрэва з n вузламі. Кожнаму вузлу адназначна прысвойваецца значэнне ад 1 да n. Вам таксама даецца цэлае значэнне startValue, якое прадстаўляе значэнне пачатковага вузла s, і іншае цэлае destValue, якое прадстаўляе значэнне пункта прызначэння...

больш падрабязна

Абыход вертыкальнага парадку двайковага дрэва LeetCode Solution

Пастаноўка праблемы Абыход двайковага дрэва ў вертыкальным парадку. У LeetCode Solution гаворыцца – улічваючы корань двайковага дрэва, вылічыце абыход двайковага дрэва ў вертыкальным парадку. Для кожнага вузла ў пазіцыі (радок, слупок) яго левы і правы даччыныя элементы будуць знаходзіцца ў пазіцыях (радок + 1, слупок – 1) і (радок + 1, слупок + 1) адпаведна. …

больш падрабязна

Сума кораня ў лік лістка Рашэнне LeetCode

Пастаноўка праблемы Сума кораня да лісткавых лікаў LeetCode Рашэнне кажа – Вам дадзены корань двайковага дрэва, якое змяшчае толькі лічбы ад 0 да 9. Кожны шлях ад кораня да ліста ў дрэве ўяўляе сабой лік. Напрыклад, шлях ад кораня да ліста 1 -> 2 -> 3 уяўляе лік 123. Вяртае агульную суму ўсіх лікаў ад кораня да ліста. Тэст…

больш падрабязна

Двайковае дрэва Inorder Traversal LeetCode Рашэнне

Пастаноўка праблемы: абход двайковага дрэва па парадку. Рашэнне LeetCode Улічваючы корань двайковага дрэва, вярніце абход значэнняў яго вузлоў у парадку. Прыклад 1: Увод: root = [1,null,2,3] Выхад: [1,3,2] Прыклад 2: Увод: root = [] Выхад: [] Прыклад 3: Увод: root = [1] Выхад: [1] Абмежаванні: колькасць вузлоў у ...

больш падрабязна

Выраўнаваць двайковае дрэва ў звязаны спіс LeetCode Solution

Выраўнаваць двайковае дрэва ў звязаны спіс LeetCode Solution кажа, што – Улічваючы root двайковага дрэва, зраўняйце дрэва ў «звязаны спіс»:

  • «Звязаны спіс» павінен выкарыстоўваць тое ж самае TreeNode клас, дзе right даччыны паказальнік паказвае на наступны вузел у спісе і left даччыны паказальнік заўсёды null.
  • «Звязаны спіс» павінен быць у тым жа парадку, што і a Папярэдні заказ абход бінарнага дрэва.

 

Прыклад 1:

Выраўнаваць двайковае дрэва ў звязаны спіс LeetCode SolutionУваход:

 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 = left) і ўсталяваць левы паказальнік каранёвага вузла як null(root.left=null) і будзе абнаўляцца на ( root = root.right ), так што цяпер корань правы вузел паддрэва.

– гэты працэс будзе працягвацца да таго часу, пакуль усе часткі левага паддрэва не стануць правым паддрэвам. Такім чынам, двайковае дрэва будзе сплюшчаным.

 

Выраўнаваць двайковае дрэва ў звязаны спіс LeetCode Solution

Выраўнаваць двайковае дрэва ў звязаны спіс LeetCode Solution

Рашэнне 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 Solution

Пастаноўка праблемы: Дыяметр N-арнага дрэва Рашэнне LeetCode – Улічваючы корань N-арнага дрэва, вам трэба вылічыць даўжыню дыяметра дрэва. Дыяметр N-арнага дрэва - гэта даўжыня самага доўгага шляху паміж любымі двума вузламі ў дрэве. Гэты шлях можа, а можа і не...

больш падрабязна

Самы нізкі агульны продак двайковага дрэва рашэння Leetcode

Пастаноўка задачы Найніжэйшы агульны продак двайковага дрэва Рашэнне LeetCode – «Найніжэйшы агульны продак двайковага дрэва» сцвярджае, што дадзены корань двайковага дрэва і два вузлы дрэва. Нам трэба знайсці найніжэйшага агульнага продка гэтых двух вузлоў. Самая нізкая распаўсюджаная…

больш падрабязна

Запаўненне наступных правых паказальнікаў у рашэнні Leetcode кожнага вузла

Пастаноўка праблемы Запаўненне наступных правых паказальнікаў у кожным вузле Рашэнне LeetCode – «Запаўненне наступных правых паказальнікаў у кожным вузле» сцвярджае, што з улікам кораня ідэальнага двайковага дрэва нам трэба запоўніць кожны наступны паказальнік вузла на яго наступны правы вузел. Калі не будзе наступнага…

больш падрабязна

Выдаліць вузлы і вярнуць рашэнне Leetcode Forest

Пастаноўка праблемы Выдаленне вузлоў і вяртанне лесу Рашэнне LeetCode – «Выдаленне вузлоў і вяртанне лесу» сцвярджае, што з улікам кораня двайковага дрэва кожны вузел мае асобнае значэнне. Нам таксама дадзены масіў to_delete, дзе нам трэба выдаліць усе вузлы са значэннямі, якія змяшчаюцца ў ...

больш падрабязна

Аднаўленне бінарнага дрэва пошуку рашэння Leetcode

Пастаноўка праблемы Аднаўленне двайковага дрэва пошуку Рашэнне LeetCode – «Аднаўленне двайковага дрэва пошуку» сцвярджае, што дадзены корань двайковага дрэва пошуку, дзе значэнні роўна двух вузлоў памяняюцца месцамі памылкова. Нам трэба аднавіць дрэва, не змяняючы яго структуры. Прыклад: Увод: корань = [1,3,null,null,2] Выхад: [3,1,null,null,2] ...

больш падрабязна

Translate »