9ms java solution


  • 3
    M
    public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
    	if ((p.val <= root.val && q.val >= root.val)
    			|| (p.val >= root.val && q.val <= root.val)) {
    		return root;
    	} else if (p.val < root.val && q.val < root.val) {
    		return lowestCommonAncestor(root.left, p, q);
    	}else{
    		return lowestCommonAncestor(root.right, p, q);
    	}
    
    }
    

    }


  • 7
    S

    I think we just need to check if both of them are in the left side or the right side. The rest case will be one in each side or either one is ancestor, which we can simply return root.

    Version 1:

    public class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(p.val < root.val && q.val < root.val)
                return lowestCommonAncestor(root.left, p, q);
            if(p.val > root.val && q.val > root.val)
                return lowestCommonAncestor(root.right, p, q);
                
            return root;
        }
    }
    

    Version 2:

    public class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(Math.max(p.val, q.val) < root.val)
                return lowestCommonAncestor(root.left, p, q);
            if(Math.min(p.val, q.val) > root.val)
                return lowestCommonAncestor(root.right, p, q);
                
            return root;
        }
    }
    

    Or make it one line:

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            return p.val < root.val && q.val < root.val ? lowestCommonAncestor(root.left, p, q) : p.val > root.val && q.val > root.val ? lowestCommonAncestor(root.right, p, q) : root;
    }

  • 0
    M

    Your solution's core is same with mine regardless of some details.


  • 0
    L

    your answer is concise


  • 0
    S

    You're right. The idea is same, but your 1st "if" statement has 2 conditions; therefore, you will end up with checking at most 3 conditions.


  • 0
    M

    Yes.Your way is more efficient and simpler.


  • 0
    A

    Very nice... by the way, I don't think it's really 9m; when I submitted a c# solution with identical algorithm it showed 192 ms... this looked weird so I put your java code and it indeed showed 10ms, but with a message about java runtime distributions unavailable, I guess they have some bug over there...


Log in to reply
 

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