การส่งผ่านคำสั่งในแนวตั้งของ Binary Tree LeetCode Solution

คำชี้แจงปัญหา การข้ามเส้นแนวตั้งของต้นไม้ไบนารี โซลูชัน LeetCode กล่าวว่า – เมื่อพิจารณาถึงรากของต้นไม้ไบนารีแล้ว ให้คำนวณการข้ามผ่านของลำดับแนวตั้งของต้นไม้ไบนารี สำหรับแต่ละโหนดที่ตำแหน่ง (แถว, col) ลูกด้านซ้ายและด้านขวาจะอยู่ที่ตำแหน่ง (แถว + 1, col – 1) และ (แถว + 1, col + 1) ตามลำดับ …

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

รวมรูทกับหมายเลขลีทโค้ดโซลูชั่น

คำชี้แจงปัญหา Sum Root to Leaf Numbers โซลูชัน LeetCode กล่าวว่า – คุณจะได้รับรากของต้นไม้ไบนารีที่มีตัวเลขตั้งแต่ 0 ถึง 9 เท่านั้น แต่ละเส้นทางจากรากสู่ใบในต้นไม้แสดงถึงตัวเลข ตัวอย่างเช่น เส้นทาง root-to-leaf 1 -> 2 -> 3 แทนตัวเลข 123 ส่งกลับผลรวมของตัวเลข root-to-leaf ทั้งหมด ทดสอบ …

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

Binary Tree Inorder Traversal โซลูชัน LeetCode

คำชี้แจงปัญหา: Binary Tree Inorder Traversal โซลูชัน LeetCode จากรากของต้นไม้ไบนารี ให้คืนค่าการข้ามผ่านที่ไม่เป็นระเบียบของค่าโหนด ตัวอย่างที่ 1: อินพุต: รูท = [1,null,2,3] เอาต์พุต: [1,3,2] ตัวอย่างที่ 2: อินพุต: รูท = [] เอาต์พุต: [] ตัวอย่างที่ 3: อินพุต: รูท = [1] เอาต์พุต: [1] ข้อจำกัด: จำนวนโหนดใน …

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

Graph Bipartite คืออะไร? โซลูชัน LeetCode

คำชี้แจงปัญหาคือกราฟ Bipartite LeetCode Solution- มีกราฟแบบไม่มีทิศทางที่มี n โหนด โดยที่แต่ละโหนดจะมีหมายเลขระหว่าง 0 ถึง n – 1 คุณจะได้รับกราฟอาร์เรย์ 2 มิติ โดยที่ graph[u] คืออาร์เรย์ของโหนดที่โหนด u อยู่ติดกับ. เป็นทางการมากขึ้น สำหรับแต่ละ v ในกราฟ[u] มีขอบที่ไม่มีทิศทางระหว่างโหนด u และโหนด v กราฟมี ...

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

ออกแบบ เพิ่มและค้นหาคำ โครงสร้างข้อมูล โซลูชัน LeetCode

คำชี้แจงปัญหา: ออกแบบ เพิ่มและค้นหาคำ โครงสร้างข้อมูล โซลูชัน LeetCode กล่าวว่า – ออกแบบโครงสร้างข้อมูลที่รองรับการเพิ่มคำใหม่และค้นหาว่าสตริงตรงกับสตริงที่เพิ่มไว้ก่อนหน้านี้หรือไม่ ใช้คลาส WordDictionary: WordDictionary() เริ่มต้นวัตถุ เป็นโมฆะ addWord(word) เพิ่มคำลงในโครงสร้างข้อมูล ซึ่งสามารถจับคู่ได้ในภายหลัง bool search(word) คืนค่า true หากมี ...

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

แผ่ 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

เส้นผ่านศูนย์กลางของ N-Ary Tree LeetCode Solution

คำชี้แจงปัญหา : เส้นผ่านศูนย์กลางของโซลูชัน LeetCode ของต้นไม้ N-Ary – เมื่อให้รากของต้นไม้ N-ary คุณต้องคำนวณความยาวของเส้นผ่านศูนย์กลางของต้นไม้ เส้นผ่านศูนย์กลางของต้นไม้ N-ary คือความยาวของเส้นทางที่ยาวที่สุดระหว่างสองโหนดในต้นไม้ เส้นทางนี้อาจหรือไม่ก็ได้…

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

บรรพบุรุษร่วมที่ต่ำที่สุดของโซลูชัน Leetcode แบบไบนารี

คำชี้แจงปัญหา บรรพบุรุษร่วมต่ำสุดของโซลูชัน LeetCode แบบไบนารี - "บรรพบุรุษร่วมที่ต่ำที่สุดของต้นไม้ไบนารี" ระบุว่าให้รากของต้นไม้ไบนารีและสองโหนดของต้นไม้ เราต้องหาบรรพบุรุษร่วมที่ต่ำที่สุดของโหนดทั้งสองนี้ สามัญต่ำสุด …

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

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

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

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

ลบโหนดและส่งคืน Forest Leetcode Solution

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

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

Translate »