給你一個二叉樹的根節(jié)點 root 袄秩，返回其最大路徑和
https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/
路徑 被定義為一條從樹中任意節(jié)點出發(fā)，沿父節(jié)點-子節(jié)點連接逢并，達到任意節(jié)點的序列。同一個節(jié)點在一條路徑序列中 至多出現(xiàn)一次 郭卫。該路徑 至少包含一個 節(jié)點砍聊，且不一定經(jīng)過根節(jié)點
路徑和 是路徑中各節(jié)點值的總和。
示例1：
1 / \ 2 3輸入：root = [1,2,3]
輸出：6
解釋：最優(yōu)路徑是 2 -> 1 -> 3 贰军，路徑和為 2 + 1 + 3 = 6
示例2：
-10 / \ 9 20 / \ 15 7輸入：root = [-10,9,20,null,null,15,7]
輸出：42
解釋：最優(yōu)路徑是 15 -> 20 -> 7 玻蝌，路徑和為 15 + 20 + 7 = 42
提示：
樹中節(jié)點數(shù)目范圍是 [1, 3 * 104]
-1000 <= Node.val <= 1000
Java解法
思路：
- 說實話，題目比較難理解词疼，但多看幾遍還是理解出來了
- 實際上就是從二叉樹的某個點出發(fā)俯树，使得經(jīng)過的數(shù)字之后為最大，這種試探推出結(jié)果的方式可以考慮通過回溯來控制輸出結(jié)果
- emmm贰盗，死在這上面了许饿，MD這個不是完全二叉樹，自己寫的是二叉樹工具類舵盈，坑死自己陋率，不過基本跑通了84/92個用例，菜雞
- 參考使用遞歸處理
public int maxGain(TreeNode node) {
if (node == null) {
return 0;
}
// 遞歸計算左右子節(jié)點的最大貢獻值
// 只有在最大貢獻值大于 0 時秽晚，才會選取對應(yīng)子節(jié)點
int leftGain = Math.max(maxGain(node.left), 0);
int rightGain = Math.max(maxGain(node.right), 0);
// 節(jié)點的最大路徑和取決于該節(jié)點的值與該節(jié)點的左右子節(jié)點的最大貢獻值
int priceNewpath = node.val + leftGain + rightGain;
// 更新答案
maxSum = Math.max(maxSum, priceNewpath);//這個為實際答案瓦糟，在遞歸當(dāng)中更新最大值返回
// 返回節(jié)點的最大貢獻值
return node.val + Math.max(leftGain, rightGain);
}
//錯誤示范
public static void back(Integer[] roots, int length, int index, List<Integer> path, int pathSum) {
boolean canGo = false;
//當(dāng)前節(jié)點的走法
int parent = (index - 1) / 2;
if (parent < length && roots[parent] != null && !path.contains(parent)) {
canGo = true;
path.add(parent);
if (roots[parent] < 0) {
//負數(shù)經(jīng)過之前先記錄一次
results.add(pathSum);
paths.add(new ArrayList<>(path));
}
back(roots, length, parent, path, pathSum + roots[parent]);
path.remove(path.size() - 1);
}
int left = 2 * (index + 1) - 1;
if (left < length && roots[left] != null && !path.contains(left)) {
canGo = true;
path.add(left);
if (roots[left] < 0) {
//負數(shù)經(jīng)過之前先記錄一次
results.add(pathSum);
paths.add(new ArrayList<>(path));
}
back(roots, length, left, path, pathSum + roots[left]);
path.remove(path.size() - 1);
}
int right = left + 1;
if (right < length && roots[right] != null && !path.contains(right)) {
canGo = true;
path.add(right);
if (roots[right] < 0) {
//負數(shù)經(jīng)過之前先記錄一次
results.add(pathSum);
paths.add(new ArrayList<>(path));
}
back(roots, length, right, path, pathSum + roots[right]);
path.remove(path.size() - 1);
}
if (!canGo) {
results.add(pathSum);
paths.add(new ArrayList<>(path));
}
}
image
官方解
-
遞歸
要不要遍歷某個節(jié)點就看這個節(jié)點是否大于0，大于的話則經(jīng)過它
不得不說牛逼
時間復(fù)雜度：O(N)
空間復(fù)雜度：O(N)
