LeetCode / Binary Search Tree / 235번 / Lowest Common Ancestor of a Binary Search Tree / JS

< 문제 바로가기 >

Lowest Common Ancestor of a Binary Search Tree - LeetCode

 

< 문제 간단설명 >

TreeNode인 p와 q가 주어지는데, p와 q의 가장 가까운 공통 부모노드를 찾는 문제이다.

 

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    while(root) {
        if(p.val < root.val && q.val < root.val) {
            root = root.left;
        }
        else if(p.val > root.val && q.val > root.val) {
            root = root.right;
        }
        else break;
    }

    return root;
};

---

생각보다 간단한 문제이다. 현재의 root의 값보다 p와 q모두 작다면 root를 root.left로 이동시켜준다.

현재의 root의 값보다 p와 q모두 크다면 root를 root.right로 이동시켜주면 된다.

 

BST의 특성상 루트의 값은 반드시 왼쪽 서브트리의 값들보다 크고 오른쪽 서브트리의 값들보다 작기 때문이다.

 

만약 두 조건 모두 걸리지 않는다면 root노드가 왼쪽과 오른쪽 사이에 잘 위치하고 있다는 뜻이므로 공통부모노드가 된다.