Article Attempt


  • 0
    P

    Approach #1 Depth-First Search [Accepted]

    Intuition

    We will modify DFS algorithm to return the pair of integer values.

    • First value of this pair is an 'ark' value - best sum that won't use current node.
    • Second value is best sum that will use current node - the 'continue' value.

    When we get pair for the root node, we'll just pick larger of the 2 values.

    So now we need to find a way to create this pair for every node in the tree. This way we will traverse the tree only once.

    Let's consider 'continue' part of the pair. It is the largest number from the 3 values:

    • Just current node
    • Current node + Current node's left son 'continue' part
    • Current node + Current node's right son 'continue' part

    The 'ark' part is the largest number from the next 6 values:

    • Just current node
    • Current node + Current node's left son 'continue' part
    • Current node + Current node's right son 'continue' part
    • Just current node's left son 'ark' part
    • Just current node's right son 'ark' part
    • Current node + Current node's left son 'continue' part + Current node's right son 'continue' part

    Complexity Analysis
    Let n be the number of nodes in the tree.

    • Time complexity : $$O(n)$$.
      We visit each node only once. All operations in one node take O(1) time (because arrays 'arks' and 'continues' have fixed size), so the overall time complexity is $$O(n) * O(1) = O(n)$$

    C++

    // long long prevents overflow errors
    typedef long long ll;
    
    class Solution {
    public:
        int maxPathSum(TreeNode* root) {
            pair<ll, ll> answer = dfs(root);
            return max<ll>(answer.first, answer.second);
        }
        
    private:
        pair<ll, ll> dfs(TreeNode *root)
        {
            // if root is null, return very small number
            if (!root)
                return make_pair(-3e9, -3e9);
            else
            {
                // 'ark', 'continue' for the left son
                pair<ll, ll> left = dfs(root->left);
                // 'ark', 'continue' for the right son
                pair<ll, ll> right = dfs(root->right);
                
                ll arks[] = {
                    left.first,
                    right.first,
                    left.second + right.second + (ll)(root->val),
                    left.second + root->val,
                    right.second + root->val,
                    (ll)root->val
                };
                
                ll continues[] = {
                    left.second + root->val,
                    right.second + root->val,
                    (ll)(root->val)
                };
                
                // return maximum values from 'arks' and 'continues' arrays
                return make_pair(
                    *max_element(arks, arks+6),
                    *max_element(continues, continues+3)
                );
            }
        }
    };
    

Log in to reply
 

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