[JAVA][LeetCode][Blind75] 235. Lowest Common Ancestor of a Binary Search Tree | BST | Recursion | Medium

문제 / 예제 / 제한조건 :

 

p와 q 사이에 있는 Value를 가진 노드 중 가장 위에 있는 노드를 구하는 문제!

 

예전에는 Easy였는데, Medium 으로 바뀐듯? 

 

# 풀이

1. p와 q 범위 안에 들었다면 -> 리턴

2. 범위 안에 들지 않았다면 

  -> 노드 왼쪽 확인 후 값이 null이라면 

  -> 노드 오른쪽 확인 후 값 리턴

/**
 * 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) {
        if(root == null) return null;
        
        if(Math.min(q.val, p.val) <= root.val 
                && root.val <= Math.max(q.val, p.val)) {
            return root;
        } else {
            TreeNode leftResult = lowestCommonAncestor(root.left, p, q);
            if(leftResult != null) return leftResult;
            else return lowestCommonAncestor(root.right, p, q);
        }
    }
}

Time Complexity: O(n)
Space Complexity: O(h)
* h : BST's height