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

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

 

1 ตัวอย่าง:

Input:

 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 ถูกต้อง โหนดย่อย

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

 

โซลูชันหลาม:

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