222. Count Complete Tree Nodes

222. Count Complete Tree Nodes

 

DFS, 재귀로 품

# 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 = right
class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        def dfs(node):
            if not node:
                return 0            
            return 1+ dfs(node.left) + dfs(node.right)
        return dfs(root)

 

 

https://youtu.be/JxIf7Rs9nPw?si=wDIc78X8ZpQNMSIK

 

이 코드는 이진 트리의 총 노드 개수를 계산하는 문제를 해결하기 위해 작성된 코드입니다.

 

특히, 이진 트리가 완전 이진 트리(Complete Binary Tree)라는 특성을 활용하여 효율적으로 노드 개수를 계산하려고 합니다.

아래에서 각 부분을 설명하겠습니다.

---

문제의 핵심

1. 완전 이진 트리의 특성:
   • 완전 이진 트리는 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있으며, 마지막 레벨은 왼쪽에서 오른쪽으로 순서대로 채워져 있습니다.
   • 이 특성을 이용하면 일부 서브트리의 높이를 비교하여 전체 노드 개수를 더 빠르게 계산할 수 있습니다.
2. 시간 복잡도 최적화:
   • 일반적인 DFS 방식은 모든 노드를 방문해야 하므로 O(n).
   • 완전 이진 트리의 특성을 이용하면 O(log(n) * log(n))으로 최적화 가능.

# 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 = right
class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        # def dfs(node):
        #     if not node:
        #         return 0            
        #     return 1+ dfs(node.left) + dfs(node.right)
        # return dfs(root)

		# 트리가 비어 있으면 노드 개수는 0
        if not root: 
            return 0
		"""
        lheight: 현재 노드부터 왼쪽 서브트리의 높이를 계산.
        rheight: 현재 노드부터 오른쪽 서브트리의 높이를 계산.
        완전 이진 트리에서 왼쪽 높이와 오른쪽 높이가 같으면, 트리는 완전히 채워져 있다는 뜻
        """
        def lheight(node):
            if not node:
                return 0
            return 1+ lheight(node.left)

        def rheight(node):
            if not node:
                return 0
            return 1+ rheight(node.right)

		# 루트 노드의 왼쪽 높이(l)와 오른쪽 높이(r)를 계산
        l,r = lheight(root), rheight(root)

        # is this balanced: 트리가 완전히 채워졌는지 확인
        if l>r:
        	"""
            왼쪽 높이가 오른쪽 높이보다 크면 트리는 완전히 채워지지 않았음
			왼쪽과 오른쪽 서브트리를 재귀적으로 탐색하며, 각각의 노드 개수를 더함
            """
            return 1 + self.countNodes(root.left) + self.countNodes(root.right)
        else:
			"""
            왼쪽 높이와 오른쪽 높이가 같으면 트리는 완전히 채워져 있음
			완전 이진 트리의 노드 개수는 2^l - 1로 계산
            """
            return (2**l) - 1

 

 

 

시간 복잡도

1. 완전 이진 트리 높이 계산:
   • 높이는 O(log(n)) 시간에 계산 가능합니다.
2. 재귀 호출 횟수:
   • 각 호출에서 높이를 계산하고, 트리가 완전히 채워져 있다면 더 이상 탐색하지 않습니다.
   • 최악의 경우 높이 계산과 재귀 호출로 인해 O(log(n) * log(n))의 시간이 소요됩니다.

---

정리

• 이 코드는 완전 이진 트리의 특성을 활용해 일반적인 DFS보다 더 효율적으로 노드 개수를 계산합니다.
• 트리가 완전히 채워져 있으면 수식을 통해 바로 계산((2^l) - 1)하고, 그렇지 않으면 재귀적으로 나머지 노드를 탐색합니다.
• 이 방법은 완전 이진 트리에서 매우 효율적이며, 트리의 높이에 비례하는 성능을 제공합니다.