Cpp go through the tree once, I like cpp can use reference as parameter to return result!


  • 0
    C
    class Solution {
    public:
        int dfs(int &result, TreeNode* root) {
            if (!root) return 0;
            int left_max = max(dfs(result, root->left), 0);
            int right_max = max(dfs(result, root->right), 0);
            result = max(result, left_max + right_max + root->val);
            return max(max(left_max, right_max) + root->val, 0);
        }
        int maxPathSum(TreeNode* root) {
            int result = INT_MIN;
            dfs(result, root);
            return result;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.