Leetcode Java Lowest Common Ancestor of a Binary Search Tree
업데이트:
문제
코드
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while ((root.val - p.val) * (root.val - q.val) > 0) {
root = root.val > p.val ? root.left : root.right;
}
return root;
}
}
결과
설명
-
주어진 이진 탐색 트리(BST)인 root에서 TreeNode p와 q의 최소의 공통된 부모 노드인 LCA를 찾는 문제이다.
- 주어진 TreeNode인 root의 val 값에 p의 val 값을 뺀 값과 root의 val 값에 q의 val 값을 뺀 값이 0보다 큰 경우 root의 노드가 해당 노드보다 큰 val 값을 가진 경우이므로, 아래를 수행하고 반복을 계속 수행한다.
- root의 val 값이 p의 val 값보다 큰 경우, root의 left TreeNode를 root에 넣어준다.
- root의 val 값이 p의 val 값보다 같거나 작은 경우, root의 right TreeNode를 root에 넣어준다.
- 반복이 완료되면 최소의 공통된 부모 노드를 저정한 root를 주어진 문제의 결과로 반환한다.
소스
Sample Code는 여기에서 확인 가능합니다.
댓글남기기