HELP!!!How many level of recursion can i use in Leetcode. Why a recursion of 5000 levels caused a StackoverflowError


  • 0
    Y

    Runtime Error Message:
    Line 25: java.lang.StackOverflowError
    Last executed input:
    5000
    [[0,1],[1,2],[2,3],[3,4],[4,5],[5,6],[6,7],[7,8],[8,9],[9,10],[10,11],[11,12],[12,13],[13,14],[14,15],[15,16],[16,

    it is a tree in the form of a straight line, that caused StackOverflow.

    I changed root from 0 to 2500. then my code is accepted.

    Just 5000 level recursion. R U Kidding me ???

    On leetcode, how deep a recursion can go?

    And when we cod in Java. How deep of a recursion can be regarded as safety?

    thank u~


  • 0
    Y

    this is my code .
    in the dfs part, if i use dfs(0,0,0), i got a StackoverFlow,but a dfs(n>>1,n>>1,0) will be accepted with beating 92%

    public class Solution {
        int max(int a,int b){return a>b?a:b;}
        ArrayList<Integer>[] to;
        int [] len;
        int []dp;
        int dfs1(int p,int fa)
        {
            if(dp[p]>=0)return dp[p];
            dp[p]=0;
            for(int i=0;i<to[p].size();i++)
            {
                int t=to[p].get(i);
                if(t==fa) continue;
                dp[p]=max(dp[p],dfs1(t,p)+1);
            }
            return dp[p];
        }
        void dfs(int p,int fa,int pre)
        {
            int m1=-1,m2=-1;
            for(int i=0;i<to[p].size();i++)
            {
                int t=to[p].get(i);
                if(t==fa)continue;
                int l=dfs1(t,p);
                if(l>m1)
                {
                    m2=m1;m1=l;
                }else
                if(l>m2) m2=l;
            }
            if(m1==-1)
            {
                len[p]=pre;return;
            }
          
            len[p]=max(pre,1+m1);
            for(int i=0;i<to[p].size();i++)
            {
                int t=to[p].get(i);
                if(t==fa)continue;
                if(dfs1(t,p)==m1) dfs(t,p,max(pre+1,m2+2));
                else dfs(t,p,max(pre+1,m1+2));
            }
        }
        public List<Integer> findMinHeightTrees(int n, int[][] e) {
            to=new ArrayList[n];
            for(int i=0;i<n;i++) to[i]=new ArrayList<>();
            for(int i=0;i<n-1;i++) {
                to[e[i][0]].add(e[i][1]);
                to[e[i][1]].add(e[i][0]);
            }
            dp=new int[n];Arrays.fill(dp,-1);
            len=new int[n];
            //dfs1(0,0);
           
            dfs(0,0,0);
            List<Integer>ans=new ArrayList<>();
            int k=0;
            for(int i=1;i<n;i++)
            k=len[i]<len[k]?i:k;
            for(int i=0;i<n;i++)
            if(len[k]==len[i]) ans.add(i);
            return ans;
        }
    }
    

  • 0
    A

    @yaoxiang3.1g Recursion is inherently unsafe. The stack depth is not a static space. In real life scenario, it is dynamic all the time. Especially for embedded systems, most coding standards explicitly forbid recursive function.


Log in to reply
 

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