之前華為面試的是遇到了讓求二叉樹最大路徑和，讓說一下大緻的思路，當時這道題目成功的通過了。這裡我來詳細歸納整理一下對應思路。
求最值的問題基本上都有一個通用的解法，那就是暴力，如果我們在解題的時候沒有更好的思路，最終可能要嘗試暴力的解法，畢竟“你能做出來，和你什麼都不做”是有很大的差别的。
求最值的問題我的第一反應是動态規劃，動态規劃主要就是用于求最值的問題，但是這裡的題目是二叉樹，二叉樹通常的解法是遞歸，基本所有的二叉樹類的問題都是可以通過遞歸架構來解決的，然後需要根據情況來判斷是前序中序後序等不同的周遊。下面寫的就是一個正常的遞歸架構。
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)其實就是要求出左子樹的最優子結構，我們常在動态規劃中看到最優子結構的，它是一類求最值問題的特性，并不是動态規劃特有的。