Tech for good

완전 이진 트리(Complete Binary Tree)의 노드 개수를 세는 문제이며, 최적화된 방법을 사용하여 O(n)보다 빠른 시간 복잡도로 해결해야 한다.완전 이진 트리는 왼쪽부터 차곡차곡 채워지는 성질이 있기 때문에, 일반적인 트리 탐색(O(n))이 아니라, 이진 탐색을 활용한 O(log n * log n) 알고리즘을 사용할 수 있다.완전 이진 트리는 모든 레벨이 가득 차 있으며, 마지막 레벨은 왼쪽부터 채워진 상태이다.즉 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이가 같다면, 트리가 완전하게 채워진 형태라는 뜻이다. 다시 말해, 전체 노드 개수 == 꽉 찬 부분(완전한 트리) + 마지막 레벨의 노드 개수이다.이렇게 노드가 모두 꽉 차 있는 완전 트리의 경우, 개수를 구하는 공식은 아래와 같다. ..

https://neetcode.io/problems/lowest-common-ancestor-in-binary-search-tree NeetCode neetcode.io공통 조상 찾기!🔹 BST(Binary Search Tree)의 특징 활용BST(이진탐색트리)에서는 왼쪽 서브트리의 모든 값이 루트보다 작고, 오른쪽 서브트리의 모든 값이 루트보다 큽니다.따라서, LCA를 찾는 과정에서 다음 규칙을 사용할 수 있습니다.p.val과 q.val이 모두 현재 노드보다 작으면, LCA는 왼쪽 서브트리에 있음.p.val과 q.val이 모두 현재 노드보다 크면, LCA는 오른쪽 서브트리에 있음.p.val과 q.val이 현재 노드 양쪽에 걸쳐 있다면, 현재 노드가 LCA임.# Definition for a binar..

# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int: if not root: return 0 total = 0 # 왼쪽 자식이 리프 노드라면 값 추가 if root.left and not root.left.l..