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

/ 리트코드, 기술 기사 / 에 의해

Python, C++, JavaScript, SQL 및 TypeScript의 다양한 LeetCode 솔루션을 살펴보세요. 여러 프로그래밍 언어로 인터뷰 준비, 학습 및 코드 연습에 적합합니다. Github 레포 링크

중간

이진 검색 트리(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에 존재할 것이다.

파이썬

				
					# 이진 트리 노드에 대한 정의. # 클래스 TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None 클래스 솔루션: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': p.val < root.val이고 q.val < root.val이면 self.lowestCommonAncestor(root.left, p, q)를 반환합니다. p.val > root.val이고 q.val > root.val이면 self.lowestCommonAncestor(root.right, p, q)를 반환합니다. root를 반환합니다.

관련 기사