Comment on page

# 124.Binary-Tree-Maximum-Path-Sum

## 题目描述

Given a non-empty binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.
Example 1:
Input: [1,2,3]
1
/ \
2 3
Output: 6

## 代码

### Approach #1 Recursion

Complexity Analysis
• Time complexity : O(N) where `N` is number of nodes, since we visit each node not more than 2 times.
• Space complexity :O(log(N)). We have to keep a recursion stack of the size of the tree height, which is O(log(N)) for the binary tree.
class Solution {
int max_sum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
max_gain(root);
return max_sum;
}
public int max_gain(TreeNode node) {
if (node == null) return 0;
int left_gain = Math.max(max_gain(node.left), 0);
int right_gain = Math.max(max_gain(node.right), 0);
// 1. the maximum value contianing the current node
int price_newpath = node.val + left_gain + right_gain;
// 2. compare the maximu vlaue
max_sum = Math.max(max_sum, price_newpath);
// 3. Return a single path through the current node
return node.val + Math.max(left_gain, right_gain);
}
}