(Tree, Medium) Lowest Common Ancestor of a Binary Search Tree

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/

LCA(Lowest Common Ancestor) 찾는 문제.
두 노드 간의 최저 공통 조상이란, 두 노드를 모두 자식으로 갖는 가장 깊은 조상을 의미한다(후손에는 자신도 포함할 수 있음).

핵심 아이디어

• root가 p보다 크고 q보다도 크다
  ==> root는 BST상에서 왼쪽 서브트리로 깊어질 수 있다.

• root가 p보다 작고 q보다도 작다
  ==> root는 BST상에서 오른쪽 서브트리로 깊어질 수 있다.

• 둘 다 아니라면, root는 p와 q사이에 존재하는 값이므로
  root 자체가 최저 공통 조상이 될 수 있다.

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 (root.val < p.val && root.val < q.val) {
            return lowestCommonAncestor(root.right, p, q);
        }
        return root;
    }
}