LeetCode - Lowest Common Ancestor of a Binary Search Tree in JavaScript

가장 가까이에 있는 공통 부모를 찾는 문제이다.

인터넷 풀이는 나한테 생각보다 조금 어려웠다. 하지만 조금더 쉽게 다가가는 방법이 있다.

두가지 풀이를 써본다.

 

문제

위의 이진 트리에서 2, 8이 주어졌을때 공통분모는 6이다.

위의 이지 트리에서 2, 4가 주어졌을때 공통분모는 2이다.

 

output이 6, 2 이런식으로 나오면 된다.

 

Andy Gala 코드 https://www.youtube.com/watch?v=VSuZoj4YC1E

var lowestCommonAncestor = function(root, p, q) { 
    let result = null;
    
    function dfs(node) {
        if (node ===null) return false;
        
        const left = dfs(node.left);
        const right = dfs(node.right);
        
        const current = p === node || q === node;
        
        if (left + right + current >= 2) return result = node;
        
        return left || right || current;
    }
    
    dfs(root);
    return result;
 }

 

내 코드

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

 

무엇이 더 적절한지는 잘모르겠지만 하나씩 풀이를 해보면 다음과 같다.

앤디의 전략은 dfs를 사용하여 접근한다. left + right + current가 2 이상일때 즉 p, q를 모두 찾았을 때 해당 노드를 result에 저장하고 반환한다.

 

나는 조금 다르게 접근했다.

정말 간단하게 p, q가 갈라지는 분기점을 공통부모로 반환했다.

 

끝!