4ms One-pass DFS C++ solution


  • 15
    R

    Simple idea: Use an array to save the "level sum" by level, then do post-processing

    class Solution {
    public:
        int depthSumInverse(vector<NestedInteger>& nestedList) {
            vector<int> result;
            for(auto ni : nestedList) {
                dfs(ni, 0, result);
            }
            //post processing 
            int sum = 0;
            for(int i = result.size()-1,level = 1; i >=0; i--, level++) {
                sum += result[i]*level;
            }
            
            return sum;
        }
        
    private:
        void dfs(NestedInteger &ni, int depth, vector<int> & result) {
            if(result.size() < depth+1) result.resize(depth+1);
            if(ni.isInteger()) {
                result[depth] += ni.getInteger();
            } else {
                for(auto n_ni : ni.getList()) {
                    dfs(n_ni, depth+1, result);
                }
            }
            
        }
        
        
    };

  • 0

    This is more efficient than two pass method. Nice!


Log in to reply
 

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