ปัญหา
กำหนด Binary Tree หาผลรวมค่าของทุก node
ตัวอย่าง: Tree: 2→right→4→left=3, right=5 → Sum = 2+4+3+5 = 14
วิธีแก้: Recursive DFS
อัลกอริทึม
- ฟังก์ชัน recurse(node): คืนค่า sum ของ subtree rooted at node
- val = node.val
- ถ้ามี left child: val += recurse(left)
- ถ้ามี right child: val += recurse(right)
- คืนค่า val
- Main: ถ้า root เป็น None → 0, ไม่งั้น recurse(root)
โค้ด Python
class TreeNode:
def __init__(self, data, left=None, right=None):
self.val = data
self.left = left
self.right = right
class Solution:
def recurse(self, node):
val = node.val
if node.left:
val += self.recurse(node.left)
if node.right:
val += self.recurse(node.right)
return val
def solve(self, root):
if not root:
return 0
return self.recurse(root)
# ทดสอบ
ob = Solution()
root = TreeNode(2)
root.right = TreeNode(4)
root.right.left = TreeNode(3)
root.right.right = TreeNode(5)
print(ob.solve(root)) # 14
ความซับซ้อน
- Time: O(n) - เยี่ยมทุก node 1 ครั้ง
- Space: O(h) - recursion stack
Iterative Versions
DFS with Stack
def solve_iterative_dfs(self, root):
if not root:
return 0
total = 0
stack = [root]
while stack:
node = stack.pop()
total += node.val
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return total
BFS with Queue
from collections import deque
def solve_iterative_bfs(self, root):
if not root:
return 0
total = 0
q = deque([root])
while q:
node = q.popleft()
total += node.val
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return total
ประยุกต์ใช้
Tree aggregation: sum, count, max, min, average - pattern เดียวกันเปลี่ยน operation
