C# - 2 solutions - iterative DFS using 2 stacks - recursive


  • 0

    one stack to hold nodes and second stack to hold depth

        public int DepthSum(IList<NestedInteger> nestedList) 
        {
            if (nestedList == null) return 0;
            Stack<IList<NestedInteger>> listStack = new Stack<IList<NestedInteger>>();
            Stack<int> depthStack = new Stack<int>();
            
            listStack.Push(nestedList);
            depthStack.Push(1);
            
            int sum = 0;
            while (listStack.Count > 0)
            {
                IList<NestedInteger> list = listStack.Pop();
                int depth = depthStack.Pop();
                
                foreach (NestedInteger n in list)
                {
                    if (n.IsInteger())
                    {
                        sum += depth * n.GetInteger();
                    }
                    else
                    {
                        listStack.Push(n.GetList());
                        depthStack.Push(depth + 1);
                    }
                }
            }
            
            return sum;
        }
    

    and here is the much simpler recursive solution

        public int DepthSum(IList<NestedInteger> nestedList) 
        {
            return DepthSum(nestedList, 1);
        }
        
        public int DepthSum(IList<NestedInteger> nestedList, int level) 
        {
            int sum = 0;
            foreach (NestedInteger x in nestedList)
            {
                if (x.IsInteger()) 
                {
                    sum += level * x.GetInteger();
                }
                else 
                {
                    sum += DepthSum(x.GetList(), level + 1);
                }
            }
            return sum;
        }
    

Log in to reply
 

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