遞歸

/*** 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 ans = INT_MIN;int dfs(TreeNode* node) {if (node == nullptr) return 0;int left = max(dfs(node->left), 0); // 左子樹最大鏈和int right = max(dfs(node->right), 0); // 右子樹最大鏈和ans = max(node->val + left + right, ans); // 兩條鏈拼成路徑return max(left, right) + node->val;}int maxPathSum(TreeNode* root) {dfs(root);return ans;}
};

時間復雜度：O(n)，其中 n 為二叉樹的節點個數。
空間復雜度：O(n)。最壞情況下，二叉樹退化成一條鏈，遞歸需要 O(n) 的棧空間。