這個問題來自 leetcode，可以在這里找到。我正在閱讀以下問題的解決方案
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int maxPathSum(TreeNode* root) {
int res = INT_MIN;
dfs(root, res);
return res;
}
int dfs(TreeNode* root, int& res)
{
if(!root)
return 0;
auto l = max(0, dfs(root->left, res)), r = max(0, dfs(root->right, res));
res = max(res, l r root->val);
return max(l, r) root->val;
}
};
我幾乎理解這個問題的邏輯，但我不太明白為什么我們0在左右子樹中的搜索部分有最大值。有人可以向我解釋嗎？
uj5u.com熱心網友回復：
該運算式l r root->val考慮了最高參與節點是當前節點的最佳路徑。
考慮到這條最佳路徑可能不包括來自左子樹的節點。在這種情況下，我們要確保它l是 0。這就是這個max(0, dfs(root->left, res))運算式所要完成的。
更具體地說，如果以節點的左子節點結束的最優向上路徑結果為負，那么用當前節點的值進一步向上擴展該路徑不是最優的。所以然后使用 0 代替，這實際上意味著我們不使用左子樹中的任何值。
顯然，確定值的原因r是類似的。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/522068.html
標籤：C 算法二叉树
上一篇：將資料從一個表拆分到另一個表