สมมติว่าเรามีรูทของไบนารีทรี แต่ละโหนดในทรีมีค่าเฉพาะ หลังจากลบโหนดทั้งหมดที่มีค่าใน to_delete เราจะเหลือฟอเรสต์ เราต้องหารากของต้นไม้ในป่าที่เหลืออยู่ ดังนั้นหากอินพุตเป็นแบบ
ถ้าอาร์เรย์ to_delete เหมือนกับ [3,5] ผลลัพธ์จะเป็น
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดความละเอียดของอาร์เรย์
- กำหนดวิธีการแก้ปัญหา () ซึ่งจะใช้โหนด to_delete อาร์เรย์และข้อมูลประเภทบูลีนที่บอกว่าโหนดเป็นรูทหรือไม่ วิธีการจะทำหน้าที่ดังต่อไปนี้−
- ถ้าโหนดเป็น null ให้คืนค่า null
- flag :=true ถ้าค่าของโหนดอยู่ใน to_delete array
- หากแฟล็กเป็นเท็จและ is_root เป็นจริง ให้แทรกโหนดลงใน res
- ซ้ายของโหนด :=แก้ (ซ้ายของโหนด to_delete ตั้งค่าสถานะ)
- ด้านขวาของโหนด :=แก้ (ด้านขวาของโหนด, to_delete, แฟล็ก)
- คืนค่า none เมื่อตั้งค่าแฟล็ก มิฉะนั้น จะเป็นเท็จ
- เรียกเมธอด Solve() จากเมธอดหลัก เช่น Solve(node, to_delete, true)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
คลาส Solution(object):def delNodes(self, root, to_delete):""" :type root:TreeNode :type to_delete:List[int] :rtype:List[TreeNode] """ to_delete =set(to_delete ) self.res =[] self.solve(root,to_delete,True) คืนค่า self.res def แก้ปัญหา (self,node,to_delete,is_root):ถ้าไม่ใช่โหนด:ส่งคืนไม่มีแฟล็ก =node.val ใน to_delete หากไม่ใช่แฟล็กและ is_root:self.res.append(node) node.left =self.solve(node.left,to_delete,flag) node.right =self.solve(node.right,to_delete,flag) คืนค่า None หากตั้งค่าสถานะเป็นโหนดอื่นอินพุต
[1,2,3,4,5,6,7][3,5]ผลลัพธ์
[[1,2,null,4],[6],[7]]
