هڪ بائنري ڳولا جو وڻ Leetcode حل جو گهٽ ۾ گهٽ عام ابڙو

مسئلي جو بيان: هڪ بائنري سرچ ٽري جو گهٽ ۾ گهٽ عام اباڙ Leetcode حل - ڏنو ويو هڪ بائنري سرچ ٽري (BST)، BST ۾ ڏنل ٻن ڏنل نوڊس جو گهٽ ۾ گهٽ عام اباڙ (LCA) نوڊ ڳوليو. نوٽ: “سڀ کان گھٽ عام ابجد ٻن نوڊس p ۽ q جي وچ ۾ بيان ڪيو ويو آھي جيئن T ۾ گھٽ ۾ گھٽ نوڊ جنھن ۾ p ۽ q ٻئي آھن…

وڌيڪ پڙهڻ

هڪ بائنري وڻ جي نوڊ کان ٻئي LeetCode حل تائين قدم قدم جي هدايتون

مسئلي جو بيان: بائنري ٽري نوڊ کان ٻئي ليٽ ڪوڊ حل تائين قدم بہ قدم ھدايتون - توھان کي ڏنو ويو آھي ھڪڙي بائنري وڻ جو روٽ n نوڊس سان. هر نوڊ منفرد طور تي 1 کان n تائين هڪ قدر مقرر ڪيو ويو آهي. توهان کي پڻ ڏنو ويو آهي هڪ عدد startValue جيڪو شروعاتي نوڊ جي قيمت جي نمائندگي ڪري ٿو، ۽ هڪ مختلف انٽيجر destValue جيڪو منزل جي قيمت جي نمائندگي ڪري ٿو ...

وڌيڪ پڙهڻ

بائنري وڻ LeetCode حل جو عمودي آرڊر ٽرورسل

مسئلي جو بيان ورٽيڪل آرڊر ٽرورسل آف بائنري ٽري LeetCode حل چوي ٿو - بائنري وڻ جي روٽ کي ڏنو وڃي، حساب ڪريو بائنري وڻ جي عمودي آرڊر ٽرورسل. هر نوڊ جي پوزيشن تي (قطار، ڪال)، ان جي کاٻي ۽ ساڄي ٻار جي پوزيشن تي هوندا (قطار + 1، col - 1) ۽ (قطار + 1، col + 1). …

وڌيڪ پڙهڻ

Sum Root to Leaf Numbers LeetCode Solution

مسئلي جو بيان Sum Root to Leaf Numbers LeetCode Solution چوي ٿو - توھان کي ھڪڙي بائنري وڻ جو روٽ ڏنو ويو آھي جنھن ۾ صرف 0 کان 9 تائين عدد آھن. وڻ ۾ هر روٽ کان پني وارو رستو هڪ انگ جي نمائندگي ڪري ٿو. مثال طور، روٽ کان پني وارو رستو 1 -> 2 -> 3 نمبر 123 جي نمائندگي ڪري ٿو. سڀني روٽ کان پني جي انگن جو مجموعي مجموعو واپس ڪريو. ٽيسٽ…

وڌيڪ پڙهڻ

Binary Tree Inorder Traversal LeetCode Solution

مسئلي جو بيان: بائنري ٽري ان آرڊر ٽرورسل ليٽ ڪوڊ جو حل بائنري وڻ جي روٽ کي ڏنو وڃي، ان جي نوڊس جي قدرن جي ان آرڊر ٽرورسل کي واپس ڏيو. مثال 1: Input: root = [1,null,2,3] Output: [1,3,2] Example 2: Input: root = [] Output: [] Example 3: Input: root = [1] Output: [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]

 

الگورتھم -

IDEA -

  • هڪ بائنري وڻ کي برابر ڪرڻ لاءِ، اسان سڀ کان پهريان کاٻي سبٽري جي ساڄي پاسي واري عنصر کي ڳولينداسين ۽ ساڄي پاسي واري عنصر حاصل ڪرڻ کان پوءِ اسان ان نوڊ جي ساڄي پوائنٽر کي ڏنل وڻ جي ساڄي سبٽري سان ڳنڍينداسين.
  • قدم 2 ۾ اسان روٽ نوڊ جي ساڄي پوائنٽر کي کاٻي-سب ٽري سان ڳنڍينداسين ۽ کاٻي-سب ٽري کي null طور سيٽ ڪنداسين.
  • مرحلا 3 ۾ هاڻي اسان جو روٽ نوڊ هڪ ساڄي-سب ٽري نوڊ آهي ساڳيو عمل هن نوڊ سان ٿيندو ۽ اهو عمل اڃا تائين جاري رهندو جيستائين سڀئي کاٻي حصا null نه ٿي وڃن.

لنڪ ٿيل لسٽ ليٽ ڪوڊ حل لاءِ فليٽ بائنري وڻ لاءِ اپروچ -

- پهرين ۾، مان هڪ لوپ هلائيندس يعني while(root!= null) پوءِ ٻه ويريئبل کڻندس ۽ کاٻي-سب ٽري کي اسٽور ڪندس.

- پوءِ چيڪ ڪندو کاٻي-سب ٽريءَ جي ساڄي نوڊ لاءِ جڏهن (k.left != null) استعمال ڪندي ۽ ان نوڊ کي ساڄي سب ٽري سان ڳنڍيندو (k.right = root.right) استعمال ڪندي.

- پوءِ روٽ نوڊ جي ساڄي پوائنٽر کي کاٻي سب ٽري (root.right = کاٻي) سان ڳنڍيو ۽ روٽ نوڊ جي کاٻي پوائنٽر کي null (root.left=null) سان سيٽ ڪريو ۽ (root = root.right) ذريعي اپڊيٽ ڪيو ويندو، تنهنڪري هاڻي روٽ صحيح آهي. subtree node.

- اھو عمل جاري رھندو جيستائين سڀ کاٻي-سب ٽري حصا ساڄي ذيلي وڻ بڻجي وڃن. ان ڪري، بائنري جو وڻ چٽو ٿيندو.

 

بائنري وڻ کي جڙيل لسٽ ۾ فليٽ ڪريو LeetCode حل

بائنري وڻ کي جڙيل لسٽ ۾ فليٽ ڪريو LeetCode حل

پٿون حل:

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

جاوا حل:

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)

خلائي پيچيدگي: اي (1)

جيئن ته اسان صرف هڪ ڀيرو گذري چڪا آهيون، وقت جي پيچيدگي o (n) هوندي.

۽ جيئن ته اسان ڪا اضافي جاءِ نه ورتي آهي، خلائي پيچيدگي o(1) مسلسل اضافي جاءِ هوندي.

ساڳيو سوال- https://www.tutorialcup.com/interview/linked-list/flattening-linked-list.htm

N-Ary وڻ LeetCode حل جو قطر

مسئلي جو بيان: N-Ary وڻ جو قطر LeetCode حل - هڪ N-ary وڻ جي روٽ کي ڏنو ويو، توهان کي وڻ جي قطر جي ڊيگهه کي ڳڻڻ جي ضرورت آهي. N-ary وڻ جو قطر ڪنهن به ٻن نوڊس جي وچ ۾ سڀ کان ڊگھي رستي جي ڊيگهه آهي. هي رستو ٿي سگهي ٿو يا نه ...

وڌيڪ پڙهڻ

هڪ بائنري وڻ Leetcode حل جو گهٽ ۾ گهٽ عام اباڙ

مسئلي جو بيان The Lowest Common Ancestor of a Binary Tree LeetCode Solution – “Lowest Common Ancestor of a Binary Tree” ٻڌائي ٿو ته بائنري وڻ جي پاڙ ۽ وڻ جا ٻه نوڊ ڏنا ويا آهن. اسان کي انهن ٻن نوڊس جي سڀ کان گهٽ عام ابجد ڳولڻ جي ضرورت آهي. گھٽ ۾ گھٽ عام…

وڌيڪ پڙهڻ

هر نوڊ ليٽ ڪوڊ حل ۾ ايندڙ ساڄي پوائنٽن کي آباد ڪرڻ

مسئلي جو بيان هر نوڊ ۾ ايندڙ ساڄي پوائنٽن کي آباد ڪرڻ LeetCode حل - ”هر نوڊ ۾ ايندڙ ساڄي پوائنٽرز کي آباد ڪرڻ“ ٻڌائي ٿو ته مڪمل بائنري وڻ جو روٽ ڏنو ويو آهي ۽ اسان کي ضرورت آهي ته نوڊ جي هر ايندڙ پوائنٽر کي ان جي ايندڙ ساڄي نوڊ تي آباد ڪرڻ. جيڪڏهن ڪو اڳتي نه آهي ...

وڌيڪ پڙهڻ

ختم ڪريو نوڊس ۽ واپسي ٻيلو ليٽ ڪوڊ حل

مسئلي جو بيان نوڊس کي ختم ڪريو ۽ ٻيلو واپس آڻيو LeetCode حل - "نوڊس کي ختم ڪريو ۽ ٻيلو واپس آڻيو" ٻڌائي ٿو ته بائنري وڻ جي روٽ ڏني وئي جتي هر نوڊ کي الڳ قدر آهي. اسان کي هڪ صف پڻ ڏني وئي آهي، to_delete، جتي اسان کي سڀني نوڊس کي ختم ڪرڻ جي ضرورت آهي جنهن ۾ موجود قدرن سان ...

وڌيڪ پڙهڻ

Translate »