← 返回 bytedance 的题目列表Binary Tree Maximum Path Sum (and Print the Path)
类型：online_judge
Given the root of a binary tree, a path is a sequence of nodes where each consecutive pair is connected by a parent-child edge. The path does not need to pass through the root and may start and end at any nodes, but it must contain at least one node.
Return the maximum path sum.
Follow-up: Output any path (as a sequence of node values) that achieves the maximum sum.
Input: level-order nodes, using null for missing children.
Output:
Line 1: maximum path sum
Line 2: one maximum-sum path (space-separated values).
Constraints: 1 <= N <= 2e5, node values in [-1e9, 1e9]
Example Input:
-10 9 20 null null 15 7
Output (one possible):
42
15 20 7
Example
Input
-10 9 20 null null 15 7
Output
42
15 20 7