ორობითი ხის LeetCode ამოხსნის ვერტიკალური რიგის გადაკვეთა

პრობლემის განცხადება ორობითი ხის ვერტიკალური რიგის გადაკვეთა LeetCode Solution ამბობს – ბინარული ხის ფესვის გათვალისწინებით, გამოთვალეთ ბინარული ხის ვერტიკალური რიგის გადაკვეთა. თითოეული კვანძისთვის პოზიციაზე (მწკრივი, სვეტი), მისი მარცხენა და მარჯვენა ბავშვები იქნებიან პოზიციებზე (მწკრივი + 1, col – 1) და (სტრიქონი + 1, col + 1) შესაბამისად. …

წაიკითხე მეტი

ჯამი ფესვიდან ფოთლამდე რიცხვებში LeetCode Solution

ამოცანის ამონაწერი ჯამი ფესვიდან ფოთლის რიცხვამდე LeetCode Solution ამბობს – თქვენ გეძლევათ ორობითი ხის ფესვი, რომელიც შეიცავს მხოლოდ 0-დან 9-მდე ციფრებს. ხეში თითოეული ფესვიდან ფოთლამდე ბილიკი წარმოადგენს რიცხვს. მაგალითად, ფესვიდან ფოთლამდე ბილიკი 1 -> 2 -> 3 წარმოადგენს რიცხვს 123. დააბრუნეთ ყველა ფესვიდან ფოთლის რიცხვის ჯამი. ტესტი…

წაიკითხე მეტი

Binary Tree Inorder Traversal LeetCode Solution

პრობლემის ფორმულირება: ორობითი ხის რიგითი გადაკვეთა 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 საფეხურზე ჩვენ დავუკავშირებთ ძირეული კვანძის მარჯვენა მაჩვენებელს მარცხენა ქვეხეს და ვაყენებთ მარცხენა ქვეხეს როგორც null.
  • მე-3 საფეხურზე ახლა ჩვენი ძირეული კვანძი არის მარჯვენა ქვეხის კვანძი, იგივე პროცესი მოხდება ამ კვანძთან და პროცესი კვლავ გაგრძელდება მანამ, სანამ ყველა მარცხენა ნაწილი არ გახდება გაუქმებული.

ორობითი ხის გაბრტყელების მიდგომა დაკავშირებულ სიაში Leetcode Solution –

– თავდაპირველად მე გავუშვებ ციკლს, ანუ while(root != null) შემდეგ ავიღებ ორ ცვლადს და შეინახავს მარცხენა ქვეხეს.

– შემდეგ შეამოწმებს მარცხენა ქვეხის ყველაზე მარჯვენა კვანძს while(k.left != null) გამოყენებით და დააკავშირებს ამ კვანძს მარჯვენა ქვეხესთან (k.right = root.right).

– შემდეგ დააკავშირეთ ძირეული კვანძის მარჯვენა მაჩვენებელი მარცხენა ქვეხესთან (root.right = მარცხნივ) და დააყენეთ ძირეული კვანძის მარცხენა მაჩვენებელი null (root.left=null) და განახლდება (root = root.right) ასე რომ, ახლა root არის მარჯვენა ქვეხის კვანძი.

– ეს პროცესი გაგრძელდება მანამ, სანამ მარცხენა ქვეხის ყველა ნაწილი არ გახდება მარჯვენა ქვეხე. ამრიგად, ორობითი ხე გაბრტყელდება.

 

გააბრტყელეთ ორობითი ხე დაკავშირებულ სიაში LeetCode Solution

გააბრტყელეთ ორობითი ხე დაკავშირებულ სიაში LeetCode Solution

პითონის გადაწყვეტა:

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)

სივრცის სირთულე: O (1)

რადგან ჩვენ მხოლოდ ერთხელ გავიარეთ, დროის სირთულე იქნება o(n).

და რადგან ჩვენ არ ავიღეთ დამატებითი სივრცე, სივრცის სირთულე იქნება o(1) მუდმივი დამატებითი სივრცე.

მსგავსი კითხვა - https://www.tutorialcup.com/interview/linked-list/flattening-linked-list.htm

ორობითი ხის Leetcode გადაწყვეტის ყველაზე დაბალი საერთო წინაპარი

პრობლემის განცხადება ბინარული ხის ყველაზე დაბალი საერთო წინაპარი LeetCode Solution – „ორობითი ხის ყველაზე დაბალი საერთო წინაპარი“ აცხადებს, რომ მოცემული ორობითი ხის ფესვი და ხის ორი კვანძი. ჩვენ უნდა ვიპოვოთ ამ ორი კვანძის ყველაზე დაბალი საერთო წინაპარი. ყველაზე დაბალი საერთო…

წაიკითხე მეტი

შემდეგი მარჯვენა მაჩვენებლების დასახლება თითოეულ კვანძში Leetcode Solution-ში

პრობლემის განცხადება შემდეგი მარჯვენა მაჩვენებლების დასახლება თითოეულ კვანძში LeetCode Solution – „შემდეგი მარჯვენა მაჩვენებლების დასახლება თითოეულ კვანძში“ აცხადებს, რომ სრულყოფილი ბინარული ხის ფესვის გათვალისწინებით და ჩვენ უნდა შევავსოთ კვანძის ყოველი შემდეგი მაჩვენებელი მის შემდეგ მარჯვენა კვანძზე. თუ არ არის შემდეგი…

წაიკითხე მეტი

წაშალეთ კვანძები და დააბრუნეთ Forest Leetcode Solution

პრობლემის განცხადება Delete Nodes და Return Forest LeetCode Solution – “Delete Nodes and Return Forest” აცხადებს, რომ მოცემული ორობითი ხის ფესვი, სადაც თითოეულ კვანძს აქვს განსხვავებული მნიშვნელობა. ჩვენ ასევე გვეძლევა მასივი, to_delete, სადაც უნდა წავშალოთ ყველა კვანძი მნიშვნელობებით, რომლებიც შეიცავს…

წაიკითხე მეტი

ორობითი ძიების ხე Leetcode Solution-ის აღდგენა

პრობლემის განცხადება Recover Binary Search Tree LeetCode Solution – „აღდგენა ორობითი ძიების ხე“ აცხადებს, რომ მოცემული იქნება ბინარული საძიებო ხის ფესვი, სადაც ზუსტად ორი კვანძის მნიშვნელობები შეცდომით იცვლება. ჩვენ უნდა აღვადგინოთ ხე მისი სტრუქტურის შეცვლის გარეშე. მაგალითი: შეყვანა: root = [1,3,null,null,2] გამომავალი: [3,1,null,null,2] …

წაიკითხე მეტი

სიმეტრიული ხე Leetcode გადაწყვეტა

პრობლემის ფორმულირება სიმეტრიული ხე LeetCode Solution – „სიმეტრიული ხე“ აცხადებს, რომ მოცემული ორობითი ხის ფესვი და ჩვენ უნდა შევამოწმოთ მოცემული ორობითი ხე არის თუ არა საკუთარი თავის სარკე (სიმეტრიული მისი ცენტრის გარშემო) თუ არა? თუ დიახ, ჩვენ უნდა დავაბრუნოთ true წინააღმდეგ შემთხვევაში, false. მაგალითი:…

წაიკითხე მეტი

დაითვალეთ კარგი კვანძები ორობითი ხის Leetcode ხსნარში

პრობლემის განცხადება ამ პრობლემასში მოცემულია ორობითი ხე თავისი ფესვით. ხეში X კვანძს დაერქვა კარგი, თუ ფესვიდან X- ს გზაზე არ არსებობს X– ზე მეტი მნიშვნელობის კვანძი. ჩვენ უნდა დავუბრუნოთ კარგი კვანძების რაოდენობა in

წაიკითხე მეტი

Translate »