What might I be doing wrong ?


  • 0

    The approach I take is perform a post order traversal and at the last check if the current node is equivalent to one of the nodes given in parameter. I soon increment if I find a node and if I have found all two, I just paste the current node in a variable and keep on returning. Please let me know if you find anything wrong in my implementation. I think the running time here should be O(n) and space complexity should be O(h) where h is the height of the tree.

    public class Solution {
        int numVal=0;
        TreeNode found = null;
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root==null)
                return null;
            findLCA(root,p,q);
            
            return null;
        }
        public void findLCA(TreeNode root, TreeNode p, TreeNode q){
            if(root==null)
                return;
            findLCA(root.left,p,q);
            if(numVal==2)
                return;
            findLCA(root.right,p,q);
            if(numVal==2)
                return;
            if(root==p )
                numVal++;
            else if(root==q)
                numVal++;
            if(numVal==2)
                found = root;
        }
    }

  • 0
    T

    From first glance, your code seems to be always returning null. Just looking the following four lines. findLCA does your logic but it doesn't return anything. Then you just return null.

    if(root==null)
        return null;
    findLCA(root,p,q);
    
    return null;

  • 0

    Thanks @totolipton ... I got carried away by the implementation that I didn't bother to look at what I wrote in the lowestCommonAcenstor. :)


Log in to reply
 

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