Can somebody tall me why my DFS code causes "StackOver Flow" error when the depth of tree is more than 6000!


  • 0
    Z
    public int longestConsecutive(TreeNode root) {
            List<Integer> res = new LinkedList<>();
            res.add(Integer.MIN_VALUE);
            //null pointer case
            if(root==null)return 0;
                //initialize the dfs
            dfs(root, root, root.val,res,1);
            return res.get(0);
        }
        public void dfs(TreeNode rootNode, TreeNode cur, int PrevNum, List res, int curLength){
            //base case
            if(cur==null){res.add(Math.max((Integer)(res.remove(0)),curLength));}
            //if this is not consecutive, compare it with res, save this as rootNode (greedy)
            else if(cur.val!=PrevNum+1){rootNode = cur; int prevMax = (Integer)(res.remove(0));res.add(Math.max(prevMax,curLength)); dfs(rootNode,rootNode.left,rootNode.val, res, 1);dfs(rootNode,rootNode.right,rootNode.val, res, 1);}
            else{
            //if this is consecutive! then keep the old rootNode, keep extending its length
            //search left
            dfs(rootNode,cur.left,rootNode.val, res, curLength+1);
            //search right
            dfs(rootNode,cur.right,rootNode.val, res, curLength+1);
            }
        }
    

Log in to reply
 

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