แทรกลงในรายการที่เชื่อมโยงแบบวงกลมที่เรียงลำดับแล้ว LeetCode Solution

คำชี้แจงปัญหา: แทรกลงในรายการที่เชื่อมโยงแบบวงกลมที่เรียงลำดับ โซลูชัน LeetCode - กล่าวว่าเมื่อได้รับโหนดรายการที่เชื่อมโยงแบบวงกลมซึ่งเรียงลำดับจากน้อยไปมาก ให้เขียนฟังก์ชันเพื่อแทรกค่า insertVal ลงในรายการเพื่อให้ยังคงเป็นรายการแบบวงกลมที่จัดเรียง โหนดที่กำหนดสามารถเป็น ...

อ่านเพิ่มเติม

แผ่ Binary Tree ให้แบนเพื่อแสดงรายการที่เชื่อมโยง LeetCode Solution

แผ่ Binary Tree ให้แบนเพื่อแสดงรายการที่เชื่อมโยง LeetCode Solution กล่าวว่า - ให้ root ของไบนารีทรี แผ่ต้นไม้ให้เป็น "รายการที่เชื่อมโยง":

  • “รายการที่เชื่อมโยง” ควรใช้เหมือนกัน TreeNode ชั้นที่ right ตัวชี้ลูกชี้ไปที่โหนดถัดไปในรายการและ left ตัวชี้ลูกอยู่เสมอ null.
  • “รายการที่เชื่อมโยง” ควรอยู่ในลำดับเดียวกับ a สั่งซื้อล่วงหน้า ข้ามผ่าน ของต้นไม้ไบนารี

 

1 ตัวอย่าง:

แผ่ Binary Tree ให้แบนเพื่อแสดงรายการที่เชื่อมโยง LeetCode SolutionInput:

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

Output:

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

2 ตัวอย่าง:

Input:

 root = []

Output:

 []

3 ตัวอย่าง:

Input:

 root = [0]

Output:

 [0]

 

อัลกอริทึม –

ความคิด -

  • ในการทำให้ไบนารีทรีแบนราบ ก่อนอื่นเราจะหาองค์ประกอบขวาสุดของทรีย่อยทางซ้าย และหลังจากที่เราได้องค์ประกอบทางขวาสุดแล้ว เราจะเชื่อมโยงตัวชี้ทางขวาของโหนดนั้นกับทรีย่อยทางขวาของทรีย่อยที่กำหนด
  • ในขั้นตอนที่ 2 เราจะเชื่อมโยงตัวชี้ทางขวาของโหนดรูทกับทรีย่อยทางซ้าย และตั้งค่าทรีย่อยทางซ้ายเป็นโมฆะ
  • ในขั้นตอนที่ 3 ตอนนี้โหนดรูทของเราเป็นโหนดทรีย่อยด้านขวา กระบวนการเดียวกันกับที่จะเกิดขึ้นกับโหนดนี้ และกระบวนการจะดำเนินต่อไปจนกว่าส่วนด้านซ้ายทั้งหมดจะกลายเป็นโมฆะ

แนวทางสำหรับ Flatten Binary Tree เพื่อเชื่อมโยงรายการ Leetcode Solution –

– ในตอนแรก ฉันจะเรียกใช้ลูปเช่น while(root != null) จากนั้นจะรับสองตัวแปรและเก็บทรีย่อยทางซ้าย

– จากนั้นจะตรวจสอบโหนดขวาสุดของทรีย่อยซ้ายโดยใช้ while(k.left != null) และจะเชื่อมโยงโหนดนั้นกับทรีย่อยทางขวาโดยใช้ (k.right = root.right)

– จากนั้นเชื่อมโยงตัวชี้ขวาของโหนดรูทกับทรีย่อยทางซ้าย (root.right = left) และตั้งค่าตัวชี้ซ้ายของโหนดรูทเป็น null(root.left=null) และจะอัปเดตโดย ( root = root.right ) ดังนั้นตอนนี้ root ถูกต้อง โหนดย่อย

– กระบวนการนี้จะดำเนินต่อไปจนกว่าส่วนทรีย่อยด้านซ้ายทั้งหมดจะกลายเป็นทรีย่อยด้านขวา ดังนั้นไบนารีทรีจะแบนราบ

 

แผ่ Binary Tree ให้แบนเพื่อแสดงรายการที่เชื่อมโยง LeetCode Solution

แผ่ Binary Tree ให้แบนเพื่อแสดงรายการที่เชื่อมโยง 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 – “รายการที่เชื่อมโยงคี่คู่” ระบุว่าให้รายการที่เชื่อมโยงเดี่ยวที่ไม่ว่างเปล่า เราจำเป็นต้องจัดกลุ่มโหนดทั้งหมดที่มีดัชนีคี่เข้าด้วยกัน ตามด้วยโหนดที่มีดัชนีคู่ และส่งคืนรายการที่จัดลำดับใหม่ โปรดทราบว่าลำดับสัมพัทธ์ภายในทั้ง ...

อ่านเพิ่มเติม

เพิ่มโซลูชัน Leetcode สองหมายเลข

คำชี้แจงปัญหา The Add Two Numbers II LeetCode Solution – “Add Two Numbers II” ระบุว่ารายการเชื่อมโยงที่ไม่ว่างเปล่าสองรายการแสดงถึงจำนวนเต็มที่ไม่เป็นลบสองจำนวนโดยที่ตัวเลขที่สำคัญที่สุดมาก่อนและแต่ละโหนดมีหนึ่งหลักเท่านั้น เราต้องบวกตัวเลขสองตัวและส่งคืนผลรวมเป็น ...

อ่านเพิ่มเติม

LRU Cache Leetcode Solution

คำชี้แจงปัญหา แคช LRU โซลูชัน LeetCode – “แคช LRU” ขอให้คุณออกแบบโครงสร้างข้อมูลตามแคชที่ใช้ล่าสุด (LRU) น้อยที่สุด เราจำเป็นต้องใช้คลาส LRUCache ที่มีฟังก์ชันต่อไปนี้: LRUCache(ความจุ int): เตรียมใช้งานแคช LRU ด้วยความจุขนาดบวก int get(int key): ส่งคืนค่า …

อ่านเพิ่มเติม

ผสาน k เรียงลำดับรายการ Leetcode Solution

คำชี้แจงปัญหา The Merge k Sorted Lists โซลูชัน LeetCode – “Merge k Sorted Lists” ระบุว่าให้อาร์เรย์ของ k ลิสต์ที่เชื่อมโยง โดยที่แต่ละรายการที่ลิงก์มีค่าที่เรียงลำดับจากน้อยไปหามาก เราจำเป็นต้องรวมรายการ k-linked ทั้งหมดเข้าเป็นรายการลิงก์เดียวและส่งคืน ...

อ่านเพิ่มเติม

การเติมพอยน์เตอร์ขวาถัดไปในแต่ละโหนด Leetcode Solution

คำชี้แจงปัญหา การเติมพอยน์เตอร์ขวาถัดไปในแต่ละโหนด โซลูชัน LeetCode – “การเติมตัวชี้ขวาถัดไปในแต่ละโหนด” ระบุว่าให้รากของต้นไม้ไบนารีที่สมบูรณ์แบบ และเราจำเป็นต้องเติมตัวชี้ถัดไปแต่ละตัวของโหนดไปยังโหนดถัดไปทางขวา ถ้าไม่มีรายต่อไป…

อ่านเพิ่มเติม

ลบโหนดที่ N ออกจากจุดสิ้นสุดของรายการ Leetcode Solution

คำชี้แจงปัญหา The Remove Nth Node From End of List Leetcode Solution – ระบุว่าคุณได้รับส่วนหัวของรายการที่เชื่อมโยง และคุณจำเป็นต้องลบโหนดที่ n ออกจากส่วนท้ายของรายการนี้ หลังจากลบโหนดนี้แล้ว ให้ส่งคืนส่วนหัวของรายการที่แก้ไข ตัวอย่าง: อินพุต: …

อ่านเพิ่มเติม

ลบองค์ประกอบรายการที่เชื่อมโยง Leetcode โซลูชัน

คำชี้แจงปัญหาในปัญหานี้เราได้รับรายการที่เชื่อมโยงกับโหนดที่มีค่าจำนวนเต็ม เราจำเป็นต้องลบบางโหนดออกจากรายการซึ่งมีค่าเท่ากับวาล ปัญหาไม่จำเป็นต้องได้รับการแก้ไขในสถานที่ แต่เราจะหารือเกี่ยวกับแนวทางดังกล่าว ตัวอย่างรายการ = …

อ่านเพิ่มเติม

Palindrome Linked List Leetcode โซลูชัน

ในปัญหา“ Palindrome Linked List” เราต้องตรวจสอบว่ารายการที่เชื่อมโยงเป็นจำนวนเต็มเดี่ยวที่ระบุเป็น palindrome หรือไม่ ตัวอย่าง List = {1 -> 2 -> 3 -> 2 -> 1} true คำอธิบาย # 1: รายการคือ palindrome เนื่องจากองค์ประกอบทั้งหมดตั้งแต่เริ่มต้นและย้อนกลับคือ ...

อ่านเพิ่มเติม

Translate »