C++, DFS, O(1) space, very little change to the last question's solution


  • 0
    T

    Idea is simple, non-reverse sum + reverse sum = sum without multiplying depth * (max depth + 1)

    Take [1. [4, [6]]] for exmple:
    Non- reverse sum = 1 * 1 + 4 * 2 + 6 * 3
    reverse sum = 1 * 3 + 4 * 2 + 6 * 1
    Non-reverse sum + reverse sum = 1 * 4 + 4 * 4 + 6 * 4 = (sum without multiplying depth) * (max depth + 1)

    //#3 DFS, reverseSum = totalSum * (max_depth + 1) - non_reverseSum
        void helper(vector<NestedInteger>& nestedList, int& res, int& res_total, int depth, int& max_depth)
        {
            max_depth = max(max_depth, depth);
            for(auto& nest: nestedList)
            {
                if(nest.isInteger()) 
                {
                    res += depth * nest.getInteger();
                    res_total += nest.getInteger();
                }
                else helper(nest.getList(), res, res_total, depth + 1, max_depth);
            }
        }
        int depthSumInverse(vector<NestedInteger>& nestedList) {
            int res = 0, res_total = 0, max_depth = 0;
            helper(nestedList, res, res_total, 1, max_depth);
            return res_total * (max_depth + 1) - res;
        }
    

  • 0

    @TonyLic It doesn't satisfy the purpose, but the idea is awesome :)


Log in to reply
 

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