Comment on page

124.Binary-Tree-Maximum-Path-Sum

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);
}
}