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

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

Lowest Common Ancestor of a Binary Search Tree - LeetCode

이진 탐색 트리에서 가장 가까운 공통 조상을 찾는 문제이다.

알고리즘 순서는 다음과 같다.
1. 주어진 root를 시작으로 BFS를 진행한다.
1-1. 이 때 unordered_map을 사용해서 parent 정보를 저장하고 방문체크를 위한 visit을 초기화한다.
2. parent를 사용해서 노드 p부터 root까지 방문 체크를 한다.
3. 노드 q부터 조상을 탐색하며 방문 체크가 된 지점을 반환한다.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        unordered_map<int, TreeNode*> parent;
        unordered_map<int, bool> visit;
        parent[root->val] = NULL;
        visit[root->val] = false;

        TreeNode* curNode;
        
        queue<TreeNode*> que;
        que.push(root);
        while (!que.empty()) {
            curNode = que.front();
            que.pop();
            if (!curNode) continue;
            
            que.push(curNode->left);
            que.push(curNode->right);
            
            if (curNode->left){
                parent[curNode->left->val] = curNode;    
                visit[curNode->left->val] = false;
            }
            if (curNode->right){
                parent[curNode->right->val] = curNode;            
                visit[curNode->right->val] = false;
            }
        }
        curNode = p;
        while (curNode){
            visit[curNode->val] = true;
            curNode = parent[curNode->val];
        }
        curNode = q;
        while (!visit[curNode->val]){
            curNode = parent[curNode->val];
        }
        
        return curNode;
    }
};

 

 

---

이번주부터 다시 알고리즘 공부 시작

leetcode 첫 문제이고 쉬워보여서 접근했으나 혼쭐이 난 문제이다. 어제부터 잡고있던 문제인데 bruteforce의 방식으로 모든 조상을 확인하는 방식으로 진행했다.