Blind 75 | Lowest Common Ancestor of a Binary Search Tree (Trees 5 / 11)

 

알고리즘

 

BST인 문제일 때에는 값을 비교하며 left로 갈지 rgiht으로 갈지 생각하면 된다

 

첫 예시의 경우 만약 p = 0, q = 4라 가정하면 둘 다 6보다 작기에 left로 간다

 

p = 7, q = 9라 가정하면 둘 다 6보다 크기에 right으로 간다.

 

만약 둘다 작거나 크지 않다면 그 사이에 있다는 뜻이므로 그대로 리턴한다.

 

예시 2에서와 같이 root이 2라 p라서 같은 경우도 컨디션에서 안 걸리기 때문에 그대로 리턴될 수 있도록 구현한다.

 

 

구현