4 lines C++/Java/Python/Ruby


  • -1
    A

    @somil_27 said in 4 lines C++/Java/Python/Ruby:

    1,2,3,null,null,4,5,8,9,7,6,4,5

    That's not a valid binary tree.
    According to your data, element 2's children is null and null which is fine, except that 2.left which is null, has children 8 and 9 and 2.right which is null has children 7 and 6. That's a broken tree.


  • 0
    A

    This 4 line solution is pretty but its not efficient. You always walk the entire tree.

    Imagine if you're tree is enormous, but the first 2 elements are your match.
    Also consider that you find both children on the left side of a really large tree, you still walk the entire right side before popping out.

    My solution (which I'm not claiming to be the prettiest or most efficient)

    // assumes a and b and ancestor are not null
    // Time Complexity: O(n) Worst case we may have to touch every node
    // Space Complexity: O(n) Worst case if very unbalanced tree. Typical would be O(Log(n)).
    private static int findLCA(TreeNode root,
                Integer a, Integer b, Ref<TreeNode> ancestor) {
    	if (root == null)
    		return 0;
    
    	int m = 0;
    	if (a.equals(root.val))
    		m++;
    	if (b.equals(root.val))
    		m++;
    
    	if (m != 2)
    		m += findLCA(root.left, a, b, ancestor);
    	if (m != 2)
    		m += findLCA(root.right, a, b, ancestor);
    
    	if (m == 2)
    		if (ancestor.val == null)
    			ancestor.val = root;
    
    	return m;
    }

  • 0

    @aaron65 That's not a solution. There's at least something missing.


  • -1
    X

    Why would it let 'left != null && right != null' happen?


  • 0
    X

    @StefanPochmann, regarding your java solution.
    if q is descendant of p, then lowestCommonAncestor() returns immediately, if root is p.
    So q will be never found, right?


  • 0

    @xibodoh Won't be found explicitly, yes.


  • -1
    A

    @StefanPochmann What if tree contains p and it does not contain q ?


  • 0
    E

    Hi @StefanPochmann
    The above solution won't work for this:
    [37,-34,-48,null,-100,-100,48,null,null,null,null,-54,null,-71,-22,null,null,null,8]
    and 2 nodes are passed this way:
    root.left.right -100
    root.right.right 48

    Solution should be -48, code prints 37
    Surprisingly this passes leetcode tests.

    Thanks.


  • 0

    @elbek.kamol Huh? 37 is correct for that.


  • 0
    E

    @StefanPochmann
    here is the tree:
    this is the tree

    the result is shown in circle.

    Thanks.


  • 0

    @elbek.kamol You're looking at the wrong -100. You said "root.left.right -100", not "root.right.left -100".


  • 0
    Y
    This post is deleted!

  • 0
    M

    The question doesn't mention whether it has duplicates if you have a example, like
    p = 1 q = 2
    ---3
    --/ -\
    -1---4
    ---- /- \
    --- 1---2

    Your algorithm will return node 3 as the result, but actually the answer is node 4, please correct me if I am wrong


Log in to reply
 

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