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

124. Binary Tree Maximum Path Sum

---

题目地址

https://leetcode.com/problems/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);     
  }
}