二叉树中红节点间的最大路径和求解问题

你的核心思路（DFS+全局最大值）是可行的，完全不需要重构为图做BFS（BFS会因节点数量上限1e5导致超时）。问题出在DFS返回值的逻辑处理上，尤其是非红节点的路径有效性判断，以及全局最大值的更新逻辑遗漏。

代码中的关键错误 #

1. 非红节点错误返回自身值：非红节点不能作为路径端点，当左右子树都没有有效红路径时，非红节点应返回负无穷（表示无法形成有效路径的一部分），而非自身节点值。
2. 全局最大值更新遗漏场景：红节点作为路径端点时，未正确覆盖所有可能的有效路径组合；非红节点连接左右红路径时，判断逻辑存在疏漏。
3. 返回值逻辑混乱：红节点应优先保留以自身为起点的最大路径，非红节点只能传递子树的有效路径加自身值，不能单独返回自己。

修正后的代码 #

class Node:
    def __init__(self, val):
        self.val = val 
        self.left = None
        self.right = None 
        self.red = False 

class Solution:
    def solve(self, root):
        max_sum = float("-inf")
    
        def dfs(node):
            """
            返回值：以当前节点为起点（向上延伸）的最大有效路径和，仅当路径起点是红节点时有效
            无法形成有效路径时返回负无穷
            """
            if not node:
                return float("-inf")
            
            left = dfs(node.left)
            right = dfs(node.right)
            
            nonlocal max_sum
            
            if node.red:
                # 计算以当前红节点为起点的最大路径
                current_max = node.val
                if left != float("-inf"):
                    current_max = max(current_max, node.val + left)
                if right != float("-inf"):
                    current_max = max(current_max, node.val + right)
                
                # 更新全局最大值：覆盖所有红-红路径场景
                if left != float("-inf") and right != float("-inf"):
                    max_sum = max(max_sum, left + node.val + right)
                if left != float("-inf"):
                    max_sum = max(max_sum, left + node.val)
                if right != float("-inf"):
                    max_sum = max(max_sum, right + node.val)
                
                return current_max
            else:
                # 非红节点只能传递子树的有效路径（加自身值）
                possible_paths = []
                if left != float("-inf"):
                    possible_paths.append(left + node.val)
                if right != float("-inf"):
                    possible_paths.append(right + node.val)
                
                # 左右都有有效路径时，形成跨节点的红-红路径
                if left != float("-inf") and right != float("-inf"):
                    max_sum = max(max_sum, left + node.val + right)
                
                return max(possible_paths) if possible_paths else float("-inf")
                
        dfs(root)
        return max_sum

# 测试失败用例
soln = Solution()
root = Node(10)
root.left = Node(-5)
root.right = Node(20)
root.left.left = Node(4)
root.left.right = Node(3)
root.right.left = Node(1)
root.right.right = Node(6)
root.right.right.red = True
root.right.left.left = Node(-10)
root.right.left.left.red = True

print(soln.solve(root))  # 输出17，符合预期

逻辑说明 #

• DFS返回值定义：明确返回「以当前节点为起点、起点为红节点的向上延伸最大路径和」，无效场景返回负无穷。
• 红节点处理：红节点可作为路径端点或中间节点，需考虑单独自身、连接左/右子路径、同时连接左右子路径三种情况，并更新全局最大值。
• 非红节点处理：仅作为路径中间部分，只能传递子树的有效路径加自身值；若左右都有有效路径，则形成完整的红-红路径，需更新全局最大值。
• 全局最大值覆盖：包含所有合法的红-红路径场景，确保不会遗漏最优解。

内容的提问来源于stack exchange，提问作者PodGen4