สมมติว่าเรามีไบนารีทรี เราต้องตรวจสอบว่าทุกโหนดในทรียกเว้นใบไม้ มีค่าเท่ากับผลรวมของมูลค่าลูกด้านซ้ายและมูลค่าของเด็กที่ถูกต้องหรือไม่
ดังนั้นหากอินพุตเป็นแบบ
แล้วผลลัพธ์จะเป็น True
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดฟังก์ชัน dfs() สิ่งนี้จะหยั่งราก
-
ถ้ารูทเป็นโมฆะ
-
คืนค่า True
-
-
ถ้าทางซ้ายของรูทเป็นโมฆะ และทางขวาของรูทเป็นโมฆะ
-
คืนค่า True
-
-
ซ้าย :=0
-
หากรูทที่เหลือไม่เป็นโมฆะ
-
left :=ค่าของรูททางซ้าย
-
-
ขวา :=0
-
หากสิทธิ์ของรูทไม่เป็นโมฆะ
-
right :=ค่าของสิทธิ์ของรูท
-
-
คืนค่า true เมื่อ (left + right เท่ากับค่าของ root) และ dfs(left of root) เป็นจริง และ dfs(right of root) เป็นจริง
-
จากวิธีหลัก ให้ทำดังต่อไปนี้ −
-
ส่งคืน dfs(root)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class TreeNode: def __init__(self, data, left = None, right = None): self.val = data self.left = left self.right = right class Solution: def solve(self, root): def dfs(root): if root == None: return True if root.left == None and root.right == None: return True left = 0 if root.left: left = root.left.val right = 0 if root.right: right = root.right.val return (left + right == root.val) and dfs(root.left) and dfs(root.right) return dfs(root) ob = Solution() root = TreeNode(18) root.left = TreeNode(8) root.right = TreeNode(10) root.left.left = TreeNode(3) root.left.right = TreeNode(5) print(ob.solve(root))
อินพุต
root = TreeNode(18) root.left = TreeNode(8) root.right = TreeNode(10) root.left.left = TreeNode(3) root.left.right = TreeNode(5)
ผลลัพธ์
True
