29ms C++ recursive solution, beats 98%


  • 0
    M

    In my example, monoPath refers to right/left path plus root while dualPath refers to the path that formed by both right and left and root.

     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        int maxPath(TreeNode* root, TreeNode* parent, int& result) {
            if (root == NULL) {
                return INT_MIN;
            }
            else if (root -> left == NULL && root -> right == NULL) {
                result = max(result,root->val);
                return root -> val;
            }
            else {
                int leftPath = INT_MIN, rightPath = INT_MIN;
                if (root -> left != NULL) {
                    leftPath = maxPath(root -> left, root, result);
                }
                if (root -> right != NULL) {
                    rightPath = maxPath(root -> right, root, result);
                }
                
                int maxSubPath = max(leftPath, rightPath), monoPath = 0, dualPath = 0;
                monoPath = maxSubPath < 0 ? root -> val : root -> val + maxSubPath;
                
                if (leftPath < 0) leftPath = 0;
                if (rightPath < 0) rightPath = 0;
                dualPath = leftPath + rightPath + root -> val;
                result = max(result, max(monoPath, dualPath));
                
                return parent ? monoPath : dualPath;
            }
        }
        int maxPathSum(TreeNode* root) {
            int result = INT_MIN;
            maxPath(root, NULL, result);
            return result;
        }
    };
    

Log in to reply
 

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