leetcode-solution/Java/Q235LowestCommonAncestor.java at main · b-knd/leetcode-solution · 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
32
33
34
35
36
37
38
39
/*
@b-knd (jingru) on 10 August 2022 09:24:00
*/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        /*
        - stop when one of the node is found, return root
        - stop when need to go separate way (eg. p smaller need to go left, q greater need to go right: return root)
        - go left if both smaller, go right if both greater
        */
        while(root != p && root != q){
            if(p.val < root.val && q.val > root.val || p.val > root.val && q.val < root.val){
                return root;
            }
            if(p.val < root.val && q.val < root.val){
                root = root.left;
            } else {
                root = root.right;
            }
        }
        return root;
    }
}

//Runtime: 4 ms, faster than 100.00% of Java online submissions for Lowest Common Ancestor of a Binary Search Tree.
//Memory Usage: 42.9 MB, less than 97.81% of Java online submissions for Lowest Common Ancestor of a Binary Search Tree.