LeetCode Tree คำถาม: สิ่งที่คุณควรรู้

ปัญหาแผนผัง Leetcode เป็นตัวเลือกยอดนิยมสำหรับคำถามสัมภาษณ์ ต้นไม้ใช้ในโครงสร้างไฟล์ โครงสร้างองค์กร การประเมินไวยากรณ์ การเรียนรู้ของเครื่อง และแอปพลิเคชันอื่นๆ อีกมากมาย นอกจากนี้ การเรียนรู้ปัญหาเกี่ยวกับต้นไม้เป็นขั้นตอนที่ดีก่อนที่จะเรียนรู้วิธีแก้ปัญหากราฟ ในโพสต์บล็อกนี้ ฉันจะแบ่งปันสิ่งที่ฉันได้เรียนรู้จากการแก้คำถามต้นไม้ 100 ข้อบน leetcode

ประเภทของต้นไม้

ต้นไม้เป็นโครงสร้างแบบลำดับชั้นที่มีชุดของโหนดที่เชื่อมต่อกัน แต่ละโหนดสามารถเชื่อมต่อกับลูกหลายคน ได้ แต่ต้องเชื่อมต่อกับพาเรนต์หนึ่งตัวเท่านั้น นี่คือตัวอย่างของต้นไม้:

เราบอกว่าโหนดเป็นลีฟหากไม่มีลูก ใบไม้ในแผนภาพด้านบนคือ 50, 5, 22, 16, 4 และ 3

Binary Treeเป็นต้นไม้ที่แต่ละโหนดมีลูกได้ไม่เกินสองคน ลูกด้านซ้ายและลูกด้านขวา ต้นไม้ด้านบนไม่ใช่ต้นไม้ไบนารี เนื่องจากโหนด 10 และ 11 มีโหนดลูกมากกว่า 2 ลูก ตรงกันข้าม นี่คือไบนารีทรี:

Binary Search Treeคือ Binary Tree ที่แต่ละโหนดมีคุณสมบัติตรงตามคุณสมบัติของ Binary Search Tree สำหรับโหนดที่กำหนด โหนดทั้งหมดในทรีย่อยด้านซ้ายจะมีขนาดเล็กกว่าโหนดนี้ และโหนดทั้งหมดในทรีย่อยด้านขวาจะมีค่ามากกว่าโหนดนี้ นี่คือตัวอย่างของแผนผังการค้นหาแบบไบนารี:

การข้ามผ่านต้นไม้

มีอัลกอริธึมที่แตกต่างกันในการสำรวจต้นไม้ การข้ามผ่านแต่ละครั้งมีการใช้งานที่แตกต่างกันซึ่งอาจเหมาะกับประเภทปัญหาเฉพาะ

การข้ามผ่านที่ไม่เป็นระเบียบนั้นเฉพาะเจาะจงกับไบนารีทรี มันข้ามทรีย่อยด้านซ้าย ตามด้วยโหนดรูท ตามด้วยทรีย่อยด้านขวา มีการใช้ชื่อตามลำดับเนื่องจากเมื่อมีการใช้การแวะผ่านนี้ในแผนผังการค้นหาแบบไบนารี ผลลัพธ์จะเป็นรายการที่เรียงลำดับ

การเคลื่อนที่ตามลำดับของ BST ด้านบน: 1, 3, 4, 6, 7, 8, 10, 13, 14

การข้ามผ่านการสั่งซื้อล่วงหน้าจะข้ามโหนดรูทตามด้วยการข้ามทรีย่อย ในบริบทของไบนารีทรี การผ่านคำสั่งล่วงหน้าคือรูท ซ้าย ขวา

การสั่งซื้อล่วงหน้าของ BST ข้างต้น: 8, 3, 1, 6, 4, 7, 10, 14, 13

การข้ามผ่านลำดับหลังจะข้ามผ่านทรีย่อยแล้วข้ามผ่านโหนดรูท ในบริบทของไบนารีทรี การเลื่อนผ่านลำดับหลังจะเป็นซ้าย ขวา ราก การข้ามผ่านคำสั่งซื้อภายหลังของ BST ข้างต้นจะเป็นอย่างไร แสดงความคิดเห็นด้านล่าง

คำจำกัดความของ Leetcode Binary Tree

คำถาม leetcode ที่แตกต่างกันกำหนดส่วนต่อประสานที่แตกต่างกันสำหรับโครงสร้างข้อมูลและวิธีทำงานกับพวกมัน สำหรับคำถามแบบต้นไม้ คำจำกัดความที่พบบ่อยที่สุดคือคำจำกัดความแบบต้นไม้ไบนารีของ TreeNode Leetcode ให้คำจำกัดความของ TreeNode ต่อไปนี้:

class TreeNode:
     def __init__(self, val=0, left=None, right=None):
         self.val = val
         self.left = left
         self.right = right

การใช้ Traversals — ผลรวมของช่วง

มาดูกันว่าเราจะนำการข้ามผ่านเหล่านี้ไปใช้ได้อย่างไรผ่านคำถามง่ายๆ ของ LeetCode - ผลรวมของช่วง คำถามขอให้ส่งคืนผลรวมของค่าทั้งหมดของโหนดทั้งหมดในช่วงรวม [ต่ำ, สูง]

วิธีง่ายๆ ในการแก้ปัญหานี้คือการสำรวจโหนดทั้งหมด สำหรับแต่ละโหนดให้ตรวจสอบว่าอยู่ในช่วงหรือไม่ และถ้าใช่ ให้เพิ่มโหนดลงในผลรวม เนื่องจากเป็นต้นไม้เราจึงต้องใช้เส้นทางข้ามต้นไม้ เพื่อประโยชน์ในการใช้งานนี้เนื่องจากเราแค่ต้องการวิธีสำรวจต้นไม้ อัลกอริทึมการสำรวจใดๆ ก็ควรจะใช้ได้ดี

ฉันจะใช้การผ่านคำสั่งซื้อล่วงหน้า นี่คือรหัสเทียมสำหรับแนวทางที่ฉันจะใช้:

1. กรณีฐาน: หากไม่มีต้นไม้ ฉันจะคืนค่า 0 เนื่องจากไม่มีโหนดอยู่ในช่วง
2. ฉันจะตรวจสอบว่าโหนดรูทอยู่ในช่วงหรือไม่ และถ้าใช่ ฉันจะเพิ่มรูทโหนดในผลรวม
3. เรียกซ้ำเพื่อเรียกใช้ฟังก์ชันบนแผนผังย่อยด้านซ้าย เพิ่มผลลัพธ์ไปยังผลรวม
4. ทำการเรียกซ้ำเพื่อเรียกใช้ฟังก์ชันบนแผนผังย่อยด้านขวา เพิ่มผลลัพธ์ไปยังผลรวม
5. คืนผลรวม

class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        if root is None:
            return 0 
            
        valuesSum = 0 
        if root.val >= low and root.val <= high:
            valuesSum += root.val 
        
        valuesSum += self.rangeSumBST(root.left, low, high)
        valuesSum += self.rangeSumBST(root.right, low, high)
        
        return valuesSum

โซลูชันก่อนหน้าของเราใช้งานได้ นอกจากนี้ยังเป็นตัวอย่างที่ดีของวิธีการใช้การข้ามผ่าน อย่างไรก็ตาม เราได้ละเลยความจริงที่ว่าต้นไม้นั้นเป็น Binary Search Tree พิจารณาแผนผังที่มี 1,000 โหนด เช่น แผนผังต่อไปนี้:

ต้นไม้เป็นไปตามคุณสมบัติของ Binary Search Tree โหนดทั้งหมดทางด้านขวาของโหนดที่กำหนดนั้นมากกว่าโหนด อย่างไรก็ตาม อัลกอริทึมของเราไม่ได้ใช้ประโยชน์จากพร็อพเพอร์ตี้นี้ หากช่วงของค่าคือ [1, 2] อัลกอริทึมจะยังคงสำรวจโหนดทั้งหมดในแผนผัง

เราสามารถเพิ่มประสิทธิภาพอัลกอริทึมได้โดยใช้ช่วงต่ำสุดและสูงสุดเพื่อพิจารณาว่าคุ้มค่ากับการสำรวจช่วงดังกล่าวหรือไม่ เนื่องจากเราทราบว่าโหนดทั้งหมดทางด้านขวามีค่ามากกว่าโหนดปัจจุบัน เราจึงไม่จำเป็นต้องข้ามไปทางขวาหากค่าปัจจุบันมากกว่าค่าสูงสุด ในทำนองเดียวกัน ไม่จำเป็นต้องเลี้ยวซ้ายหากโหนดมีขนาดเล็กกว่าจุดต่ำสุดอยู่แล้ว นี่คือรหัสใหม่เพื่อปรับปรุงประสิทธิภาพ:

class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        if root is None:
            return 0 
            
        valuesSum = 0 
        if root.val >= low and root.val <= high:
            valuesSum += root.val 
        
        if root.val > low:
            valuesSum += self.rangeSumBST(root.left, low, high)
        if root.val < high:
            valuesSum += self.rangeSumBST(root.right, low, high)
        
        return valuesSum

การข้ามผ่านคำสั่งระดับ

สุดท้าย มีอีกหนึ่งเส้นทางที่สำคัญกว่าบนต้นไม้ที่เรียกว่าการเดินทางข้ามระดับตามลำดับ การข้ามผ่านลำดับระดับคือวิธีการสำรวจต้นไม้ตามระดับ ทีละระดับ

ลองใช้ตัวอย่าง Binary Search Tree อีกครั้ง:

ลำดับการเดินทางข้ามระดับของต้นไม้นี้คือ 8, 3, 10, 1, 6, 14, 4, 7, 13

ตรงกันข้ามกับการข้ามผ่านอื่นๆ ปกติแล้วการข้ามผ่านลำดับระดับจะดำเนินการซ้ำๆโดยใช้คิว คิวติดตามโหนดปัจจุบันทั้งหมดที่ยังไม่ผ่าน แนวคิดคือการป๊อปทีละโหนดจากคิว จากนั้นเพิ่มลูกของโหนดนี้ลงในคิว ฉันแนะนำให้เรียนรู้การข้ามผ่านตามลำดับระดับหลังจากที่คุณฝึกคำถามบางข้อด้วยรูปแบบการข้ามผ่านอื่นๆ

เช่นเดียวกับหัวข้อ leetcode เมื่อคุณเรียนรู้หัวข้อแล้ว สิ่งสำคัญคือต้องฝึกฝน ต่อไปนี้เป็นคำถาม leetcode 6 ข้อที่คุณสามารถแก้ไขได้

1. รากเท่ากับผลรวมของเด็ก
2. ใช้ Postorder Traversal
3. ใช้การข้ามคำสั่งซื้อล่วงหน้า
4. ต้นเดียวกัน
5. ตรวจสอบแผนผังการค้นหาแบบไบนารี
6. การข้ามผ่านคำสั่งระดับไบนารีทรี