題目描述：

示例：

分析題意：

1，該路徑至少包含一個節點，不一定要經過根節點，可以只是一個結點；
2，從任意節點出發，到達任意節點
3，求：所有可能路徑的最大值

測試用例：

代碼和思路分析：

后序遍歷；加到負值寧愿不加；

class Solution {int ans = INT_MIN; public :int maxPathSum(TreeNode* root) {oneSideMax(root);return ans;}int oneSideMax(TreeNode* root) { //后序遍歷if (root == nullptr) return 0; //特殊情況//看左邊 和 右邊； 如果是負數 甘愿不加 所以是加 0 ；int left = max(0, oneSideMax(root->left)); int right = max(0, oneSideMax(root->right)); ans = max(ans, left + right + root->val); //記錄但當前最大值 并更新 return max(left, right) + root->val; } };

運行結果：

總結：

最根本的。就是一個后序遍歷！

總結

以上是生活随笔為你收集整理的Leetcode 124题：求⼆叉树中最⼤路径和的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。