Binary Search Tree : Lowest Common Ancestor 풀이 Java

 

LCA : LCA알고리즘은 트리에서 두 개의 노드를 선택했을 때 최소 공통 조상을 구해주는 알고리즘이다.

LCA는 두 노드가 처음으로 갈라지는 지점이다. * 본인 포함 * 자기 자신도 자신의 조상이 될 수 있음

 

이 문제는 LCA에 대한 개념과 재귀에 대해서 알면 쉽게 풀 수 있지만

개념을 이해하지 못하면 산으로 갈 수 있다.

 

DFS 재귀로 풀기

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

class Node {
	Node left;
	Node right;
	int data;

	Node(int data) {
		this.data = data;
		left = null;
		right = null;
	}
}

class LCA_BST {

	/*
	 * class Node int data; Node left; Node right;
	 */
	public static Node lca(Node root, int v1, int v2) {
		// Write your code here.
		if (root.data > v1 && root.data > v2)
			return lca(root.left, v1, v2);
		else if (root.data < v1 && root.data < v2)
			return lca(root.right, v1, v2);
		else
			return root;
	}

	public static Node insert(Node root, int data) {
		if (root == null) {
			return new Node(data);
		} else {
			Node cur;
			if (data <= root.data) {
				cur = insert(root.left, data);
				root.left = cur;
			} else {
				cur = insert(root.right, data);
				root.right = cur;
			}
			return root;
		}
	}

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int t = scan.nextInt();
		Node root = null;
		while (t-- > 0) {
			int data = scan.nextInt();
			root = insert(root, data);
		}
		int v1 = scan.nextInt();
		int v2 = scan.nextInt();
		scan.close();
		Node ans = lca(root, v1, v2);
		System.out.println(ans.data);
	}
}