꿀잠

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

이진 트리에서 두 노드의 공통 조상 중 가장 가까운 공통 조상을 찾는 문제이다.

이진트리의 경우 좌측 노드는 현재의 값보다 작으며 우측 노드는 현재의 값보다 크다는 특징이 있다. 특정 두 노드의 공통 조상 중 가장 가까운 조상일 경우 해당 노드를 기준으로 좌, 우측에 두 노드가 있게 된다. 따라서 해당 조건으로 루트에서 노드를 따라 찾아가면 찾을 수 있다.

/**  
 * 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) {  
        int pVal = p.val;  
        int qVal = q.val;  
  
        while(root != null){  
            int curVal = root.val;  
            // 두 값 모두 현재 노드에서 왼쪽에 있는 경우.
            if(curVal > pVal && curVal > qVal){  
                root = root.left;  
			// 두 값 모두 현재 노드에서 오른쪽에 있는 경우.
            }else if(curVal < pVal && curVal < qVal){  
                root = root.right;  
            }else{  
                return root;  
            }  
        }  
  
        return root;  
    }  
  
}