fishercoderLeetcode/EASY/src/easy/LowestCommonAncestorOfABinarySearchTree.java at master · JesusCoder/fishercoderLeetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
package easy;

import classes.TreeNode;

public class LowestCommonAncestorOfABinarySearchTree {
    //After drawing out the tree and run it manually, made it AC'ed easily! Cheers!

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || p == root || q == root) return root;
        if((root.val - p.val) * (root.val - q.val) <= 0) return root;
        if((root.val - p.val) * (root.val - q.val) > 0 && (root.val - q.val) > 0) {
            return lowestCommonAncestor(root.left, p, q);
        }
        if((root.val - p.val) * (root.val - q.val) > 0 && (root.val - q.val) < 0) {
            return lowestCommonAncestor(root.right, p, q);
        }
        return root;
    }


    //cheers! so easy to made it ACed! Pretty straightforward after thinking it through. - 09/27/2016
    public TreeNode lowestCommonAncestor_again(TreeNode root, TreeNode p, TreeNode q) {
        if(p == root || q == root) return root;
        if((root.val - p.val) * (root.val - q.val) < 0) return root;
        if((root.val - p.val) * (root.val - q.val) > 0 && root.val - q.val > 0) return lowestCommonAncestor(root.left, p, q);
        if((root.val - p.val) * (root.val - q.val) > 0 && root.val - q.val < 0) return lowestCommonAncestor(root.right, p, q);
        return root;
    }


}