235. Lowest Common Ancestor of a Binary Search Tree

문제

풀이

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        int min = Math.min(p.val, q.val);
        int max = Math.max(p.val, q.val);

        if(root == null) {
            return null;
        }
        if(root.val >= min && root.val <= max) {
            return root;
        } else if(root.val < min) {
            return lowestCommonAncestor(root.right, p, q);
        } else {
            return lowestCommonAncestor(root.left, p, q);
        } 
    }
}

• p와 q 사이에 있는 노드 중, 가장 처음 탐색되는 노드가 lowest common ancestor
  • BST 특성상, p와 q가 분기되는 최초의 노드가 두 노드가 만나는 가장 낮은 조상이다.
  • p와 q가 분기되기 위해선 p와 q 사이에 있는 값이어야함
• p, q 중 큰 값과 작은 값을 찾아서, 그 사이에 있다면 root / 없다면 오른쪽 or 왼쪽 탐색