[Leetcode] 0235. 이진 탐색 트리의 최소공배조상

이진 검색 트리(BST)가 주어졌을 때, BST에서 주어진 두 노드의 가장 낮은 공통 조상(LCA) 노드를 찾으세요.

에 따르면 위키피디아의 LCA 정의: “최하위 공통 조상은 두 노드 사이에서 정의됩니다. 피 그리고 큐 가장 낮은 노드로서 티 둘 다 가지고 있어요 피 그리고 큐 후손으로서 (우리가 허용하는 곳) 자기 자신의 자손이 되는 노드).”

예시 1:

입력: 루트 = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
산출: 6
설명: 노드 2와 8의 LCA는 6입니다.

예 2:

입력: 루트 = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
산출: 2
설명: 노드 2와 4의 LCA는 2입니다. LCA 정의에 따르면 노드는 자기 자신의 자손이 될 수 있기 때문입니다.

예시 3:

입력: 루트 = [2,1], p = 2, q = 1
산출: 2

제약:

• 트리의 노드 수는 범위 내에 있습니다. [2, 10 5 ].
• -10 9 <= 노드.val <= 10 9
• 모두 Node.val ~이다 고유한.
• p != q
• 피 그리고 큐 BST에 존재할 것이다.