ให้ต้นไม้ไบนารี หาเส้นทางที่ยาวที่สุดที่ค่าโหนดต่อเนื่องกัน (เพิ่มหรือลดทีละ 1) เส้นทางอาจขึ้นไปแล้วลงมาได้
ตัวอย่าง: ต้นไม้ที่มีโหนด 3-2-4-5-6 → เส้นทางยาว 5 ([2,3,4,5,6])
อัลกอริธึม DFS
- แต่ละโหนดคืน
(inc, dec): ความยาวเส้นทางเพิ่ม/ลดต่อเนื่องที่ลงมาจากโหนดนี้ - รวมเส้นทางจากลูกซ้ายและลูกขวา: ถ้าลูกซ้าย-โหนด-ลูกขวาเป็นลำดับต่อเนื่อง ให้อัปเดต
maxPath - คืนค่า
maxPathสูงสุด
การนำไปใช้
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):
if not root: return 0
self.maxPath = 0
def helper(node):
inc = dec = 1
if node.left:
left_inc, left_dec = helper(node.left)
else:
left_inc = left_dec = 0
if node.right:
right_inc, right_dec = helper(node.right)
else:
right_inc = right_dec = 0
if node.left and node.val - node.left.val == 1:
inc = max(inc, left_inc + 1)
elif node.left and node.val - node.left.val == -1:
dec = max(dec, left_dec + 1)
if node.right and node.val - node.right.val == 1:
inc = max(inc, right_inc + 1)
elif node.right and node.val - node.right.val == -1:
dec = max(dec, right_dec + 1)
if node.left and node.right and node.left.val - node.val == 1 and node.val - node.right.val == 1:
self.maxPath = max(self.maxPath, left_dec + right_inc + 1)
elif node.left and node.right and node.left.val - node.val == -1 and node.val - node.right.val == -1:
self.maxPath = max(self.maxPath, left_inc + right_dec + 1)
self.maxPath = max(self.maxPath, inc, dec)
return inc, dec
helper(root)
return self.maxPath
# ตัวอย่างต้นไม้
root = TreeNode(3)
root.left = TreeNode(2)
root.right = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(9)
root.right.left.left = TreeNode(6)
ob = Solution()
print(ob.solve(root)) # 5
