[해커랭크] Binary Search Tree : Lowest Common Ancestor [JAVA]

문제링크 : www.hackerrank.com/challenges/binary-search-tree-lowest-common-ancestor/problem

Binary Search Tree : Lowest Common Ancestor | HackerRank

음, 일단 문제 입력조건을 믿고 풀다가 10번을 넘게 시도해도 틀린 것을 해결하지 못했었다.

입력 조건은 데이터의 크기가 25이하인데 26이 들어가더라. 나중에 확인하고 배열의 크기를 늘렸다.

하...

 

어쨌든 제대로 풀진 못한 것 같다. 

일단 작성한 init함수에서 노드의 부모와 level을  par, depth 배열에 저장해뒀다.

lca함수에서는 v1과 v2의 depth를 같게 해주고나서  v1과 v2가 같을 때까지 parent를 탐색하도록 했다.

search함수는 그 값을 루트에서 다시 찾아갔다.

더 좋은 코드를 참고하고싶었는데 해커랭크의 discussion에서 못찾았다.

public static int par[] = new int[30];
    public static int depth[] = new int[30];
    public static Node ans;
    public static void init(Node root){
        for(int i=1;i<=29;i++){
            par[i] = -1;
        }
        Queue<Node> q = new LinkedList<Node>();
        q.add(root);
        int dep = 1;
        while(!q.isEmpty()){
            int q_size = q.size();
            for(int i=0;i<q_size;i++){
                Node cur = q.poll();
                depth[cur.data] = dep;
                if(cur.left!=null){
                    par[cur.left.data] = cur.data;
                    q.add(cur.left);
                }
                if(cur.right!=null){
                    par[cur.right.data] = cur.data;
                    q.add(cur.right);
                }
            }
            dep++;
        }
        
    }
    
    public static void search(Node root, int key){
        if(root==null) return;
        if(root.data == key){
            ans = root;
            return;
        } 
        search(root.left,key);
        search(root.right,key);
    }
    
	public static Node lca(Node root, int v1, int v2) {
        init(root);
      	while(depth[v1]!=depth[v2]){
            if(depth[v1]< depth[v2]){
                int parent = par[v2];
                v2 = parent;
            }
            else if(depth[v1] > depth[v2]){
                int parent = par[v1];
                v1 = parent;
            }
        }
        while(v1!=v2){
            v1 = par[v1];
            v2 = par[v2];
        }
        search(root, v1); 
        return ans;
    }