ปัญหา
ตรวจสอบ Binary Tree ว่าทุก node (ยกเว้น leaves) มีค่าเท่ากับผลรวมของลูกซ้าย + ลูกขวา
ตัวอย่าง: Root=18, Left=8, Right=10, Left children=3,5 → 8=3+5, 18=8+10 → True
วิธีแก้: Recursive DFS
อัลกอริทึม
- ฟังก์ชัน dfs(root)
- ถ้า root เป็น None → True
- ถ้าเป็น leaf (ไม่มีลูก) → True
- left_val = root.left.val ถ้ามี left ไม่งั้น 0
- right_val = root.right.val ถ้ามี right ไม่งั้น 0
- คืนค่า: (left_val + right_val == root.val) AND dfs(left) AND dfs(right)
โค้ด Python
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 is None:
return True
if root.left is None and root.right is None:
return True
left_val = root.left.val if root.left else 0
right_val = root.right.val if root.right else 0
return (left_val + right_val == 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)) # True
# False case
root2 = TreeNode(10)
root2.left = TreeNode(4)
root2.right = TreeNode(5) # 4+5=9 ≠ 10
print(ob.solve(root2)) # False
ความซับซ้อน
- Time: O(n)
- Space: O(h)
Children Sum Property
เรียกว่า "Children Sum Property" - คุณสมบัติที่ node = sum of children
ใช้ใน: Binary Tree validation, Heap property checking, Expression trees
Iterative Version
def solve_iterative(self, root):
if not root:
return True
stack = [root]
while stack:
node = stack.pop()
if node.left is None and node.right is None:
continue
left_val = node.left.val if node.left else 0
right_val = node.right.val if node.right else 0
if left_val + right_val != node.val:
return False
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return True
