Binary Tree Maximum Path Sum
Updated
Problem statement
A path in a binary tree is a non-empty sequence of nodes in which consecutive nodes share an edge and no node appears more than once. Its sum is the total of its node values.
Given the root of a non-empty binary tree, return the maximum path sum. The path may start and end at any nodes and does not need to pass through the root.
Function
maxPathSum(root: TreeNode) → intExamples
Example 1
root = [1,2,3]return = 6The path 2 -> 1 -> 3 uses both children and has sum 6.
Example 2
root = [-10,9,20,null,null,15,7]return = 42The maximum path is 15 -> 20 -> 7, whose sum is 42.
Example 3
root = [-3]return = -3A path must contain at least one node, so the only valid answer is the root value -3.
Constraints
- The tree contains between
1and3 * 10^4nodes. -1000 <= Node.val <= 1000
More Globalization Partners Onsite Interview questions
Similar questions at other companies
- Sum of Weighted Distances in a TreeGoogle · ONSITE INTERVIEWGoogle interview questions
- File Encryption Tree OptimizationDatabricks · PHONE SCREEN · ONSITE INTERVIEWDatabricks interview questions
- Binary Tree Maximum Path SumGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions
- Binary Tree Maximum Path SumBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
- Transitive Employee Referral CountsRobinhood · ONSITE INTERVIEWRobinhood interview questions
- Maximum Nonadjacent Sum in a General TreeZip · PHONE SCREEN · ONSITE INTERVIEWZip interview questions
- Maximum Sum of Non-Adjacent Tree NodesInMobi · ONSITE INTERVIEWInMobi interview questions
- Distance Sums to Special Nodes in a Weighted TreeNutanix · ONSITE INTERVIEWNutanix interview questions
- Minimum Leaf Path Sum over All RootsInfosys · OAInfosys interview questions
- Part 2: Batch Access ReviewScale AI · OAScale AI interview questions