가장 가까운 공통 조상 - 3584번

---

풀이 방법

각 노드의 부모노드를 저장해주고 루트 노드는 그대로 0으로 두었다.

findHeight 메서드를 이용해서 두 노드의 높이를 구해주면서 루트 노드까지 가는 과정에서 만난 노드들의 높이도 저장해 주었다.

가까운 공통 조상을 구하기 위해 먼저 높이를 낮은 쪽으로 맞춰주고 한 칸씩 부모로 가면서 구해주었다.

 

내 코드

package com.company;

import java.io.*;
import java.util.*;

public class Main {
    static int[] tree, height;
    static int T, N, a, b;

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        T = Integer.parseInt(br.readLine());

        for (int tc = 0; tc < T; tc++) {
            N = Integer.parseInt(br.readLine());
            tree = new int[N + 1];
            height = new int[N + 1];

            for (int i = 0; i < N - 1; i++) {
                st = new StringTokenizer(br.readLine());
                a = Integer.parseInt(st.nextToken());
                b = Integer.parseInt(st.nextToken());
                tree[b] = a;
            }

            st = new StringTokenizer(br.readLine());
            System.out.println(NCA(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }
    }

    static int findHeight(int a) {
        int count = 1;
        if (tree[a] != 0) {
            count += findHeight(tree[a]);
        }
        height[a] = count;
        return count;
    }


    static int NCA(int a, int b) {
        findHeight(a);
        findHeight(b);

        if (height[a] < height[b]) {
            int temp = a;
            a = b;
            b = temp;
        }

        while (height[b] < height[a]) {
            a = tree[a];
        }

        while (a != b) {
            a = tree[a];
            b = tree[b];
        }

        return a;
    }

}