Binary Tree Maximum Path Sum

Given a 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 does not need to go through the root.

For example: Given the below binary tree,

1  / \ 2   3 Return 6.

递归解法

思路

树的问题一般都用递归的解法, 递归结束条件为节点为空返回sum为0. 因为最大值处理为 root, root+ left , root + right 这三种情况还可能是root+ left + right, 所以维护一个数组来存储第四种情况的值(java无法按引用传，就只能建立一个数组）

复杂度

时间O(n) 空间栈O(logn)

代码

public int maxPathSum(TreeNode root) {        int[] tem = new int[1];        tem[0] = Integer.MIN_VALUE;        helper(root, tem);        return tem[0];    }public int helper(TreeNode root, int[] tem) {        if (root == null) {            return 0;        }        int left = helper(root.left, tem);        int right = helper(root.right, tem);        int max = Math.max(Math.max(root.val + left, root.val + right), root.val);        tem[0] = Math.max(max, Math.max(root.val + left + right, tem[0]));        return max;    }