Stack overflow on OJ, Passing Locally - Recursive and Intuitive Solution


  • 0
    R

    The test case with the tree with 10,000 nodes fails on OJ, and it succeeds in 15 ms. on local box.
    I tried converting some other people's passing recursive java solutions to C# and ran on local box as well, they all ran in the same amount of time.

    So I'm not sure what is wrong with OJ.

    Here's my code:

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     public int val;
     *     public TreeNode left;
     *     public TreeNode right;
     *     public TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        
        public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
        {
            TreeNode result = null;   
            LowestCommonAncestor(root, p, q, ref result);
            
            return result;
        }
    
        public static int LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q, ref TreeNode result)
        {
            if (root == null || p == null || q == null)
                return 0;
            
            int self1 = root == p ? 1 : 0;
            int self2 = root == q ? 1 : 0;
            
            int onLeft = LowestCommonAncestor(root.left, p, q, ref result);
            if(onLeft == 2) 
                return 2;
                
            int onRight = LowestCommonAncestor(root.right, p, q, ref result);
            if(onRight == 2) 
                return 2;
            
            int sum = self1 + self2 + onLeft + onRight;
            if(sum == 2)
                result = root;
                
            return sum;
        }
    }
    

Log in to reply
 

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