Maximum Path Sum in Binary Tree
You are given the root of a binary tree. Your task is to find the maximum path sum.
A path is a sequence of connected nodes where:
- The path can start and end at any node in the tree.
- Each node can appear at most once in the path.
- The path does not need to pass through the root.
Return the maximum possible sum of values along any valid path.
Examples
Input: root = [1,2,3]
Output: 6
Explanation: The maximum path is 2 → 1 → 3 with a sum of 6.
Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The maximum path is 15 → 20 → 7 with a sum of 42.
Input: root = [-3]
Output: -3
Explanation: The only valid path consists of the single node.
Constraints
- 1 = Number of nodes = 105
- -10³ = Node.data = 10³
Companies
Topics
Solution.cs C#JavaPythonC++Javascript
Unlock the code editor
Sign in to write, run, and submit your solution against the full test suite.
- Run code against sample & hidden test cases
- Save submissions and track your streak
- Compare with editorial & community solutions