Бинардык издөө дарагынын эң төмөнкү жалпы ата-бабасы Leetcode чечими

Көйгөйдүн билдирүүсү: Бинардык издөө дарагынын эң төмөнкү жалпы ата-бабасы Leetcode чечими – Бинардык издөө дарагы (BST) берилгенде, BSTдеги эки берилген түйүндөрдүн эң төмөнкү жалпы ата-тегин (LCA) табыңыз. Эскертүү: "Эң төмөнкү жалпы ата-баба p жана q эки түйүнүнүн ортосунда T ичиндеги эң төмөнкү түйүн катары аныкталат, ал p жана q экөөнө тең ...

Толук маалымат

Бинардык дарак түйүнүнөн башка LeetCode Чечимине кадам-кадам багыттары

Көйгөйдүн билдирүүсү: Бинардык дарак түйүнүнөн башка LeetCode Чечимине кадам-кадам багыттары – Сизге n түйүндүү бинардык дарактын тамыры берилген. Ар бир түйүн уникалдуу түрдө 1ден nге чейинки мааниге ээ. Сизге ошондой эле башталгыч түйүндүн маанисин билдирген бүтүн сан startValue жана көздөгөн жердин маанисин билдирген башка бүтүн destValue берилет…

Толук маалымат

Binary Tree LeetCode Чечиминин Vertical Order Traversal

Көйгөйдүн билдирүүсү Бинардык дарактын вертикалдуу тартибин өтүү LeetCode Solution мындай дейт: - Бинарлык дарактын тамырын эске алуу менен, экилик дарактын вертикалдуу тартибин кесүү. Позициядагы ар бир түйүн үчүн (сап, кол), анын сол жана оң балдары тиешелүүлүгүнө жараша (сап + 1, кол – 1) жана (сап + 1, кол + 1) позицияларында болот. …

Толук маалымат

Тамырдан жалбырактын сандарын кошуу LeetCode Solution

Көйгөйдүн билдирүүсү Тамырдан жалбырактын сандарынын суммасы LeetCode Solution мындай дейт: - Сизге 0дөн 9га чейинки сандарды камтыган бинардык дарактын тамыры берилген. Дарактагы ар бир тамырдан жалбыракка чейинки жол бир санды билдирет. Мисалы, тамырдан жалбыракка жол 1 -> 2 -> 3 123 санын билдирет. Бардык тамырдан жалбыракка чейинки сандардын жалпы суммасын кайтарыңыз. Сыноо…

Толук маалымат

Binary Tree Inorder Traversal LeetCode Solution

Көйгөйдүн билдирүүсү: Binary Tree Inorder Traversal LeetCode чечими Бинардык дарактын тамырын эске алуу менен, анын түйүндөрдүн маанилеринин тартибин өтүүнү кайтарыңыз. 1-мисал: Киргизүү: root = [1,null,2,3] Чыгуу: [1,3,2] Мисал 2: Киргизүү: root = [] Чыгуу: [] 3-мисал: Киргизүү: root = [1] Чыгуу: [1] Чектөөлөр: түйүндөрдүн саны…

Толук маалымат

Бинардык даракты LeetCode чечими менен байланышкан тизмеге түздөө

Бинардык даракты LeetCode чечими менен байланышкан тизмеге түздөө мындай дейт - эске алуу менен root экилик дарактын, даракты "байланышкан тизмеге" түздөңүз:

  • "Шилтемеленген тизме" ошол эле колдонулушу керек TreeNode класс кайда right бала көрсөткүч тизмедеги кийинки түйүндү көрсөтөт жана left бала көрсөткүчү ар дайым null.
  • "Шилтемеленген тизме" бир эле тартипте болушу керек Алдын-ала буйрутма өтүү бинардык дарактын.

 

Мисал 1:

Бинардык даракты LeetCode чечими менен байланышкан тизмеге түздөөкиргизүү:

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

Output:

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

Мисал 2:

киргизүү:

 root = []

Output:

 []

Мисал 3:

киргизүү:

 root = [0]

Output:

 [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-Ары дарагынын диаметри LeetCode Solution

Көйгөйдүн билдирүүсү: N-Ары дарагынын диаметри LeetCode Solution – N-арий дарагынын тамырын эске алуу менен, дарактын диаметринин узундугун эсептөө керек. N-арий дарагынын диаметри дарактын каалаган эки түйүнүнүн ортосундагы эң узун жолдун узундугу. Бул жол болушу мүмкүн же жок ...

Толук маалымат

Бинардык дарактын эң төмөнкү жалпы ата-бабасы Leetcode чечими

Көйгөйдүн билдирүүсү Бинардык дарактын эң төмөнкү жалпы түпкү атасы LeetCode Solution – “Экилик дарактын эң төмөнкү жалпы атасы” экилик дарактын тамыры жана дарактын эки түйүнү берилгенин билдирет. Бул эки түйүндүн эң төмөнкү жалпы атасын табышыбыз керек. Эң төмөнкү жалпы…

Толук маалымат

Ар бир түйүн Leetcode Чечиминде кийинки оң көрсөткүчтөрдү толтуруу

Көйгөйдүн билдирүүсү Ар бир түйүнгө кийинки оң көрсөткүчтөрдү толтуруу LeetCode Solution - "Ар бир түйүнгө кийинки оң көрсөткүчтөрдү толтуруу" идеалдуу бинардык дарактын тамырын эске алуу менен, түйүндүн ар бир кийинки көрсөткүчүн анын кийинки оң түйүнүнө толтуруу керек экенин айтат. Кийинкиси жок болсо…

Толук маалымат

Түйүндөрдү жок кылуу жана Forest Leetcode Чечимин кайтаруу

Көйгөйдүн билдирүүсү Түйүндөрдү жок кылуу жана Токойду кайтаруу LeetCode Чечим - "Бүйүндөрдү жок кылуу жана Токойду кайтаруу" ар бир түйүн өзүнчө мааниге ээ болгон бинардык дарактын тамыры берилгенин айтат. Бизге ошондой эле to_delete массив берилет, анда биз камтылган маанилери бар бардык түйүндөрдү жок кылышыбыз керек ...

Толук маалымат

Translate »