If it helps the course, here’s an approach that uses half the code and that I think is simpler to understand. A given root returns two values: open_root
means that you can connect a path to its root, and closed_root
means you cannot.
def max_path_sum(root):
def dfs(root):
if not root:
return 0, 0
open_left, closed_left = dfs(root.left)
open_right, closed_right = dfs(root.right)
open_root = root.data + max(open_left, open_right, 0)
closed_root = max(closed_left, closed_right, open_left + open_right + root.data)
return open_root, closed_root
return max(dfs(root))
Course: Grokking Coding Interview Patterns in Python - AI-Powered Learning for Developers
Lesson: Solution: Binary Tree Maximum Path Sum - Grokking Coding Interview Patterns in Python