Maximum Path Sum in a Binary TreeHard
A path in a binary tree can start and end at any two nodes in the tree that are connected via a set of edges.
Given the root node of a binary tree that contains nodes with numbers, write a function that returns the maximum sum of any path in the tree.
For example, if your function is given the following binary tree, the maximum path sum is
The maximum sum can be found from the path between node 7 and node 8:
9 + 6 + 7 + 1 + 8 = 31.
Examples of Binary Tree Paths
Think of a path as a single line that can be drawn from one node to another, without needing to draw over any edge more than once.
The following is an example of a valid path in a binary tree.
Assume that every node in the tree has access to its
rightchild nodes, and no access to the parent node.