มีต้นไม้แบบทวิภาค หาเส้นทางที่สลับซ้าย-ขวา-ซ้าย... (หรือ ขวา-ซ้าย-ขวา...) ไปลงลึกที่สุด
เช่น ต้นไม้ที่มีโหนด 2,3,4,5,6,7,8 ให้ 5 เส้นทาง [2,4,5,7,8]
ขั้นตอนการแก้ปัญหา
- DFS พร้อม flag บอกทิศทางที่ควรไป (True=ซ้าย, False=ขวา)
- ถ้า flag=True: ไปซ้ายต่อเนื่อง (count+1) หรือไปขวาเริ่มใหม่ (count=1)
- ถ้า flag=False: ไปขวาต่อเนื่อง หรือไปซ้ายเริ่มใหม่
- คืนค่าสูงสุดจากรากซ้ายและรากขวา
ตัวอย่างโค้ด
class TreeNode:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
class Solution:
def solve(self, root):
if not root: return 0
def dfs(node, count, flag):
if node:
if flag:
a = dfs(node.left, count+1, False)
b = dfs(node.right, 1, True)
else:
a = dfs(node.right, count+1, True)
b = dfs(node.left, 1, False)
return max(a,b)
return count
a = dfs(root.left, 1, False)
b = dfs(root.right, 1, True)
return max(a,b)
ob = Solution()
root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
root.right.left.right = TreeNode(7)
root.right.left.right.left = TreeNode(8)
print(ob.solve(root))
อินพุต
root = TreeNode(2) ...
เอาต์พุต
5
