Рашэнне LeetCode Count Sub Islands

Пастаноўка праблемы Count Sub Islands Рашэнне LeetCode кажа, што grid1 і grid2 утрымліваюць толькі 0 (прадстаўляюць ваду) і 1 (прадстаўляюць зямлю). Востраў азначае групу з 1, злучаных 4 напрамках. Востраў у Grid2 лічыцца падвостравам, калі ёсць востраў у Grid1, які змяшчае ўсе ячэйкі, якія складаюць ...

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

Абыход вертыкальнага парадку двайковага дрэва 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

Пастаноўка праблемы - гэта двухбаковае рашэнне LeetCode Graph - Існуе неарыентаваны граф з n вузламі, дзе кожны вузел пранумараваны ад 0 да n - 1. Вам даецца 2D-граф масіва, дзе graph[u] - гэта масіў вузлоў з вузлом u. знаходзіцца побач з. Больш фармальна, для кожнага v у графе [u] існуе неарыентаванае рэбро паміж вузлом u і вузлом v. Граф мае ...

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

Дызайн Дадаць і шукаць у словах Структура дадзеных LeetCode Solution

Пастаноўка праблемы: распрацоўка структуры даных і пошук слоў у LeetCode Рашэнне кажа – Спраектуйце структуру даных, якая падтрымлівае даданне новых слоў і пошук, ці адпавядае радок любы раней дададзены радок. Рэалізаваць клас WordDictionary: WordDictionary() Ініцыялізуе аб'ект. void addWord(word) Дадае слова ў структуру даных, яно можа быць супастаўлена пазней. bool search(word) Вяртае праўду, калі ёсць ...

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

Выраўнаваць двайковае дрэва ў звязаны спіс 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 – «Запаўненне наступных правых паказальнікаў у кожным вузле» сцвярджае, што з улікам кораня ідэальнага двайковага дрэва нам трэба запоўніць кожны наступны паказальнік вузла на яго наступны правы вузел. Калі не будзе наступнага…

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

Translate »