LeetCode 222(Count Complete Tree Nodes, Python)

1. 문제 링크

• https://leetcode.com/problems/count-complete-tree-nodes/

LeetCode - The World's Leading Online Programming Learning Platform

2. 문제 설명

• 주어진 완전 이진 트리의 노드 개수를 반환하는 문제
• 완전 이진 트리란 마지막 레벨을 제외한 모든 레벨에서 노드가 왼쪽에서 오른쪽으로 채워진 이진 트리를 의미, 모든 레벨의 노드는 위부터 채워지기 때문에, 가장 아래 레벨이 아니면 무조건 노드가 모두 완전히 채워지고, 가장 아래 레벨은 빈 노드가 있을 수도 있다.

3. 처음 풀이

• 그냥 노드 개수를 모두 세는 방법. 노드의 개수는 왼쪽 서브 트리 노드 개수 + 오른쪽 서브 트리 노드 개수 + 1(현재 루트 노드) 이므로 left+right+1의 구조로 재귀함수를 적용
• 이 풀이의 경우 완전 이진 트리임을 이용하지 않았음. 하지만 그럼에도 속도가 나쁘지 않았다. 시간 복잡도는 O(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:
        if not root:
            return 0
        else:
            return self.countNodes(root.left)+self.countNodes(root.right)+1

4. 다른 풀이

• 현재 루트에서 왼쪽, 오른쪽으로 각각 쭉 내려간 깊이가 같다면, 완전히 꽉 찬 이진 트리이므로 개수를 바로 구할 수 있다. (1+2+2²+2³+…+2ⁿ⁻¹ = 2ⁿ-1)
• 그렇지 않다면 왼쪽, 오른쪽에 각각 재귀를 때린다.
• 재귀가 반복되면 언젠가 완전히 꽉 찬 이진 트리가 나오거나 트리의 끝까지 도달하게 된다.
• 시간 복잡도는 O(logn)

# 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:
        if not root:
            return 0

        left = 1
        curr = root
        while curr.left:
            curr = curr.left
            left += 1
        
        right = 1
        curr = root
        while curr.right:
            curr = curr.right
            right += 1
        
        if left == right:
            return (1 << left) - 1

        return self.countNodes(root.left) + self.countNodes(root.right) + 1

5. 배운 점

• 처음 풀이가 완전 이진 트리임을 이용하지 못하였기에 더 좋은 풀이가 있으리라 짐작했지만 시도하지 못했다. 처음 풀이 런타임이 괜찮게 나오기도 했던 이유도 있지만(테스트 케이스가 두 풀이를 구분하기에 좋지 않은 듯), 다른 풀이를 시도하지 못한 이유는 아래와 같다.
• 재귀적으로 접근할 때는 하나의 규칙으로 풀려야 한다고 생각했다.
• 즉, 다른 풀이에서는, 꽉 찬 이진 트리일 경우 (1<<left) - 1로 개수를 계산하고, 꽉 찬 이진 트리가 아닐 때는 (왼쪽)+(오른쪽)+1로 계산하였다. 그런데 이렇게 두 규칙이 섞여있을 때는 재귀적으로 풀 수 없다고 생각했다.
• 그런데 생각해보면 재귀적으로 접근할 때 종결 조건을 제일 위에서 return해주는데 사실 종결 조건도 어떻게 보면 또 하나의 규칙이다.
• 그러니까 규칙이 여러가지여도 재귀적으로 접근할 수 있다.