正文
简介【二叉树中的最大路径和】给定一个非空二叉树，返回其最大路径和。
题目描述#
给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
示例 1:
输入: [1,2,3] 1 / \ 2 3 输出: 6
示例 2:
输入: [-10,9,20,null,null,15,7] -10 / \ 9 20 / \ 15 7 输出: 42
我的代码#
class Solution { volatile int max = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { maxPathSum2(root); return max; } private int maxPathSum2(TreeNode root) { if (null != root) { int val = root.val; int left = maxPathSum2(root.left); int right = maxPathSum2(root.right); if (left < 0) { left=0; } if (right < 0) { right=0; } if (val + left + right > max) { max = val + left + right; } return (left > right) ? left + val : right + val; } else { return 0; } } }
算法#
后续#
这个编程题属于二叉树的范畴，感觉也是动态规划的问题，求解局部最优解以及全局最优解的问题。
