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

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

Lowest Common Ancestor of a Binary Search Tree - LeetCode

 

최소공통조상(LCA)을 구하는 문제이다.

워낙에 널려있는 문제라 조금만 검색하면 풀이 자체는 쉽다!

다만 여기상에서는 int 를 return 하는 것이 아닌 여기서 만들어진 구조체를 return 하는 것이라

array를 만들어서 푸는 기존 방법과는 조금 다르게 구조체를 찾아가는 과정이 필요하다.

 

먼저 root index를 0 으로 두고, 왼쪽 오른쪽을 1,2로 둔다. 나머지 tree도 이런식으로 indexing하여 그려나간다고 하자.

p와 q에 해당하는 index를 찾아준다. (indexing method)

 

그 후, p와 q의 depth가 같아질때까지 부모칸으로 옮겨주고, depth 같은 상태에서 둘의 index가 다르다면 한칸씩 둘다 위로 옮겨준다. 그때 같아지는 index가 최소공통조상이 된다.

 

최소공통조상을 구했으면 이를 가진 구조체를 찾아가야하는데,

처음에 설명한대로 tree를 만들면, 부모가 n 일 경우, 왼쪽 자식은 n*2 + 1 (홀수), 오른쪽 자식은 n*2 + 2 (짝수) 가 된다.

최소공통조상이 0이 될때까지 윗칸으로 나누어 가며, 이때 각각의 index가 홀수인지 짝수인지 stack에 저장을 한다. (다시 거꾸로 가야하므로.)

마지막으로 stack에서 하나씩꺼내며 root에서 부터 탐색해나가면 된다.

 

class Solution {
public:
    long long idx1 = -1;
    long long idx2 = -1;
    stack<int> lr;
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        indexing(root,0,p,q);
        idx1 = find(idx1,idx2);
        while (idx1>0) {
            if (idx1&1==1) lr.push(0);
            else lr.push(1);
            idx1 = (idx1-1)>>1;
        }
        while(!lr.empty()) {
            if (lr.top()==0) root = root->left;
            else root = root->right;
            lr.pop();
        }
        return root;
    }
    void indexing(TreeNode* t, long long i, TreeNode*p, TreeNode* q) {
        if (t==NULL) return;
        if (t==p) idx1 = i;
        if (t==q) idx2 = i;
        indexing(t->left, (i<<1)+1,p,q);
        indexing(t->right,(i<<1)+2,p,q);
    }
    int find(int idx1, int idx2) {
        while (idx1!=idx2) {
            int depth1 = log2(idx1+1);
            int depth2 = log2(idx2+1);
            if (depth1<=depth2) idx2 = (idx2-1)>>1;
            if (depth1>=depth2) idx1 = (idx1-1)>>1;
        }
        return idx1;
    }
};

이렇게 풀고 문제를 다시 읽어보니 binary search tree 인 것을 발견했다.

왼쪽 자식이 부모 값보다 작고 오른쪽 자식이 부모보다 큰 이진 트리인데 이를 이용하면 더 쉽고 빠르게 풀 수 있을것이다. 나중에 수정해봐야겠다..