สมมติว่าเรามีต้นไม้ไบนารี โหนดเรียกว่าไม่เพียงพอหากทุกเส้นทางจากรากถึงปลายที่ตัดกับโหนดนี้มีผลรวมน้อยกว่าขีด จำกัด อย่างเคร่งครัด เราต้องลบโหนดที่ไม่เพียงพอทั้งหมดพร้อมกัน และส่งคืนรูทของไบนารีทรีที่เป็นผลลัพธ์ ดังนั้นถ้าต้นไม้นั้นเหมือน และขีดจำกัดคือ 1 −
จากนั้นต้นไม้ผลลัพธ์จะเป็น −
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดวิธีการแก้ปัญหา() ซึ่งจะเริ่มต้นและจำกัด
- ถ้าโหนดไม่มีแผนผังย่อยซ้ายและขวา
- ถ้าค่าของ root น้อยกว่า 1 ให้คืนค่า null มิฉะนั้น root
- ถ้ารูทออกจากทรีย่อยแล้ว ทางซ้ายของรูท :=แก้ (ด้านซ้ายของรูท ขีดจำกัด – ค่าของรูท)
- ถ้ารูทมีทรีย่อยที่ถูกต้อง ให้ทางขวาของรูท :=แก้ (ทางขวาของรูท ขีดจำกัด – ค่าของรูท)
- หากรูทมีทรีย่อยด้านซ้าย หรือทรีย่อยด้านขวาหรือทั้งสองอย่าง ให้คืนค่ารูท มิฉะนั้นจะเป็นค่าว่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class Solution(object): def sufficientSubset(self, root, limit): """ :type root: TreeNode :type limit: int :rtype: TreeNode """ if not root.left and not root.right: return None if root.val<limit else root if root.left: root.left= self.sufficientSubset(root.left,limit-root.val) if root.right: root.right = self.sufficientSubset(root.right,limit-root.val) return root if root.left or root.right else None
อินพุต
[1,2,3,4,-99,-99,7,8,9,-99,-99,12,13,-99,14] 1
ผลลัพธ์
[1,2,3,4,null,null,7,8,9,null,14]
