[LeetCode] 235. Lowest Common Ancestor of a Binary Search Tree

       문제 요약        

- 문제

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

         아이디어        

이분 탐색 트리 

좌측 서브 트리의 모든 노드의 값 < 각 노드의 값 < 우측 서브 트리 모든 노드 값

따라서,

1) 모두 최상위 노드보다 작다면 좌측 서브 트리에서 찾기 

2) 모두 최상위 노드보다 크다면 우측 서브 트리에서 찾기 

3) 최상위 노드가 두 개의 노드 사이에 있다면 최저 공통 조상 

 

 

 

         소스코드        

 

/**
 * 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) {
       TreeNode node = root;
       while(node != null){
        if(p.val < node.val && q.val < node.val){
            node = node.left;
        }else if(node.val < p.val && node.val < q.val){
            node = node.right;
        }else {
            return node;
        }
       }
       return node;
    }
}