C++ two traverse DFS solution, it works for case like [1,[[[]]]]


  • 0
    A

    Yes. The following two BFS solution passes leetcode test cases but it doesn't pass this test case [1,[[[]]]].

    https://discuss.leetcode.com/topic/49488/java-ac-bfs-solution
    https://discuss.leetcode.com/topic/49041/no-depth-variable-no-multiplication/6

    So for me I would still prefer the following solution which get depth first and then calculate.

    class Solution {
    public:
        int calD(vector<NestedInteger> &nestedList, int currentD) {
            int ans = currentD;
            for (auto ni : nestedList)
                ans = max(ans, ni.isInteger() ? currentD + 1 : calD(ni.getList(), currentD + 1));
            return ans;
        }
        
        int helper(vector<NestedInteger> &nestedList, int d) {
            int ans = 0;
            for (auto ni : nestedList)
                ans += ni.isInteger() ? ni.getInteger() * d : helper(ni.getList(), d - 1);
            return ans;
        }
    
        int depthSumInverse(vector<NestedInteger>& nestedList) {
            int d = calD(nestedList, 0);
            return helper(nestedList, d);
        }
    };
    

Log in to reply
 

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