[B] [C] [D]

A path is defined as a sequence that starts at any node in the tree and follows parent to child nodes to reach any node. The same node appears at most once in a path sequence. The path contains at least one node and does not necessarily go through the root node.

Path and is the sum of the values of all nodes in a path.

Give you the root node of a binary tree, root, return its maximum path and.

Example 1:

Input: root = [1,2,3] Output: 6 Description: The optimal path is 2 -> 1 -> 3, and the sum of paths is 2 + 1 + 3 = 6Copy the code

Example 2:

Input: root = [-10,9,20, NULL, NULL,15,7] Output: 42 Description: The optimal path is 15 -> 20 -> 7, and the sum of paths is 15 + 20 + 7 = 42Copy the code

Tip:

  • The number of nodes in the tree ranges from[1, 3 * 104]
  • -1000 <= Node.val <= 1000

Their thinking

Each path in the binary tree has a vertex node, so by taking each node as the vertex and obtaining the maximum path sum, we get the maximum possible path sum, where the maximum value is the result value in this case.

The demo

Code implementation

Var maxPathSum = function(root) {let Max = -infinity; Function findPathSum(node){if(node === null) return 0; const left = findPathSum(node.left), right = findPathSum(node.right); Max = math.max (Max,node.val+(left>0? left:0)+(right>0? right:0)); Return node.val+ math. Max (left,right,0)} findPathSum(root); return max; };Copy the code

At this point we have completed the maximum path sum in leetcode-124-binary tree

If you have any questions or suggestions, please leave a comment!