LeetCode 124. Binary Tree Maximum Path Sum [Hard] [C++] 解題筆記

Given the root of a binary tree, return the maximum path sum.

For this problem, a path is defined as any node sequence from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1:

Input: root = [1,2,3]
Output: 6

Example 2:

Input: root = [-10,9,20,null,null,15,7]
Output: 42
  

想法:

    這題直接用遞迴從左右子樹分別找出左右子樹的最大值，然後再看看當前的 node 的 val 是否大於 0，

若大於 0 則加上當前 node 的 val。

完整程式碼:

class Solution {
public:
    int max_sum;
    int dfs(TreeNode* root) {
        if (root == nullptr) { return 0; }
        int left_sum = max(dfs(root->left), 0);
        int right_sum = max(dfs(root->right), 0);
        max_sum = max(max_sum, left_sum + right_sum + root->val);
        return max(left_sum, right_sum) + root->val;
    }
    int maxPathSum(TreeNode* root) {
        max_sum = INT_MIN;
        dfs(root);
        return max_sum;
    }
};