之前华为面试的是遇到了让求二叉树最大路径和，让说一下大致的思路，当时这道题目成功的通过了。这里我来详细归纳整理一下对应思路。
求最值的问题基本上都有一个通用的解法，那就是暴力，如果我们在解题的时候没有更好的思路，最终可能要尝试暴力的解法，毕竟“你能做出来，和你什么都不做”是有很大的差别的。
求最值的问题我的第一反应是动态规划，动态规划主要就是用于求最值的问题，但是这里的题目是二叉树，二叉树通常的解法是递归，基本所有的二叉树类的问题都是可以通过递归框架来解决的，然后需要根据情况来判断是前序中序后序等不同的遍历。下面写的就是一个常规的递归框架。
void traverse(TreeNode node) {
// 前序遍历
traverse(node.left);
// 中序遍历
traverse(node.right);
// 后序遍历
} 所以到这里，首先基本上你要确定你的算法思路，不同类型的问题通常有其常规对应的解法，这里我就打算使用树的递归来解决问题，整体思路确定了，下面就是按照这个思路框架来套，写出对应的代码。
public int maxPathSum(TreeNode root) {
int traverse = traverse(root);
return Math.max(traverse,maxValue);
}
public int maxValue = Integer.MIN_VALUE;
public int traverse(TreeNode root) {
if (root == null ) {
return 0;
}
// 左子树的最大路径,必须要大于0
int left = Math.max(traverse(root.left),0);
// 右子树的最大路径,必须要大于0
int right = Math.max(traverse(root.right),0);
// 当前节点连接左右子树形成的最大路径
maxValue = Math.max(maxValue, root.val + left + right);
// 当前节点和左子树或者和右子树连接取最大值
return Math.max(root.val + left, root.val + right);
} 执行结果
这题的解法使用的常规的树的递归，然后使用后序遍历的框架，但需要注意的是，要考虑一些逻辑细节，比如说左右子树如果小于0了，这个时候当前节点应该舍去小于0的左右子树。
总结起来有三种逻辑：
- 当前节点和左子树连接
- 当前节点和右子树连接
- 当前节点和左右子树连接。
总结一下，求最值的问题，一般都是有最优子结构的，这里的traverse(root.left)其实就是要求出左子树的最优子结构，我们常在动态规划中看到最优子结构的，它是一类求最值问题的特性，并不是动态规划特有的。