Stackoverflow in my simple Java solution ?


  • 0
    A

    Hello, I've been trying to solve this problem using a simple approach: get the 2 paths from the root to the targeted nodes, then find the common node between these 2 paths, but I get stackoverflow on the line where I push the node to the stack representing the path.
    Here's my code:

    public class Solution {
        
        // flag to be set to true if the target node was reached, thus quit
        boolean flag = false;
        Stack<TreeNode> p1 = new Stack<TreeNode>();
        Stack<TreeNode> p2 = new Stack<TreeNode>();
        
        public void getPath(TreeNode n, int x,Stack<TreeNode> s){
            if(n==null || flag)
                return;
            s.push(n);
            if(n.val==x){
                flag = true;
                return;
            }
            if(n.left==null && n.right==null){
                if(n.val!=x)
                    s.pop();
                else flag = true;
                return;
            }
            getPath(n.left,x,s);
            getPath(n.right,x,s);
            if(!flag)
                s.pop();
        }
        
        
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            
            getPath(root,p.val,p1);
            flag = false;
            getPath(root,q.val,p2);
            while(!p1.isEmpty() && !p2.isEmpty()){
                if(p1.peek()!=p2.peek()){
                    p1.pop();
                    p2.pop();
                }
                else return p1.peek();
            }
            return null;
            
        }
    }

Log in to reply
 

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