Coding Interview

[코딩 인터뷰][LeetCode] – Count Complete Tree Nodes

※ 이 포스트는 LeetCode 코딩 인터뷰 문제인 Count Complete Tree Nodes의 해설을 담고 있습니다.
본 풀이는 Optimal하지 않을 수 있으며, LeetCode에서의 Submission 통과만을 보장합니다.

문제 정보

문제 출처 : https://leetcode.com/problems/count-complete-tree-nodes/submissions/
카테고리 : Binary Search
난이도 : 쉬움 ~ 중간


문제 설명

Complete Binary Tree (마지막 level을 제외한 모든 부모 level이 완전히 채워진 Tree)가 주어졌을 때, 이 Tree의 노드 수를 출력하여라.
Tree는 노드를 추가할 때 현재 level에서 삽입 가능한 곳 중 가장 왼쪽에 우선적으로 삽입하는 방식으로 만들어졌다.


문제 풀이

SIMPLE – O(N)의 방법
이 문제를 가장 단순하게 푸는 방법은 재귀 호출을 사용하는 방식이다. 각 노드는 자신의 왼쪽, 오른쪽 자식의 정보를 left, right에 저장한다.
Tree의 Root에서 시작해서 자신의 left와 right을 root로 한 subTree의 노드 수의 합에 자기자신을 계산한 +1을 해주면 답이 나온다.
이 아이디어는 재귀적으로 구현할 수 있으며 O(N)의 시간복잡도를 가진다.

위 풀이는 Complete Binary Tree와 노드 삽입 조건 중 어떤 것도 사용하지 않았다.
이 두 조건을 가지고 이분 검색을 수행하면 O((log N)^2)의 수행시간으로 문제를 해결할 수 있다

Binaary Search – O((log N)^2)의 방법
문제 해결 절차는 다음과 같다.

1. Root를 Level 0이라 간주하고, Tree의 최대 Level을 찾는다.
노드는 가능한 왼쪽부터 삽입하기 때문에, Root로부터 왼쪽으로만 탐색할 때, 마지막으로 도달하는 노드는 항상 최대 Level에 속한다.
최대 Level을 L이라고 하면, L – 1까지 Level은 완전하므로 그 노드의 수는 2^L – 1개가 된다.

2. Level L의 노드 수를 찾는다. 가장 오른쪽 노드를 찾을 수 있다면, Level L의 전체 노드 수를 구할 수 있다.
Level L에는 2^L개의 노드가 있고, 가장 왼쪽을 인덱스 0으로 오른쪽을 2^L – 1라고 할 때 인덱스를 L개의 비트로 표현할 수 있다.
알고리즘은 그 비트를 하나씩 찾아나간다. 가장 앞자리의 비트가 1이라는 말은 Root의 오른쪽 Child의 SubTree에 노드가 존재한다는 말이다. 맨 처음에 모든 비트가 0으로 세팅된 상황에서, 가장 앞자리의 비트를 1로 세팅하고 탐색을 시작해보자. 첫 번째를 제외하고는 모두 왼쪽 Child를 선택하게 될테니 도착지점의 인덱스는 2^(L – 1)이 될 것이다. 여기에 노드가 존재하지 않는다면 가장 오른쪽 노드는 이 지점보다 왼쪽에 있다. 따라서 이 비트는 1이 아닌 0이 되어야한다.
이런 방식으로 비트를 1로 설정해 탐색을 해서 마지막에 노드를 발견하면 그대로 두고 아니면 0으로 바꾸는 방식으로 문제를 풀 수 있다.


코드

Simple – O(N)

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        # For empty tree case.
        if root == None:
            return 0
        
        # Recursively return sum of children.
        left, right = 0, 0
        if root.left != None:
            left = self.countNodes(root.left)
        if root.right != None:
            right = self.countNodes(root.right)
        return left + right + 1

Binary Search – O((log N)^2)

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        # For empty tree case.
        if root == None:
            return 0
        
        # Init Sum and Level
        Sum, L = 0, 0
        # Find Max Level
        cur = root
        while cur.left != None:
            L += 1
            cur = cur.left
        Sum = 2 ** L - 1
        
        # Binary Search and Find right most node in level L.
        Command = [0] * L
        for i in range(L):
            # Set i-th value to 1
            Command[i] = 1
            cur = root
            for cmd in Command:
                cur = cmd == 0 and cur.left or cur.right
            if cur == None:
                Command[i] = 0
        
        # Calc the number of nodes in level L.
        Command.reverse()
        for i in range(L):
            Sum += (2 ** i) * Command[i]
        
        return Sum + 1
admin

Recent Posts

2024년 11월 17일 일요일 – 서울 생활 129주차

괌여행 아내와 함께 괌으로 여행을 갔다. 출산 이후로 둘만 가는 첫 여행이다. 하와이가 일본인들이 많이…

3일 ago

2024년 11월 3일 일요일 – 서울 생활 127주차

반복적인 일상 매일 아침 일어나 회사에 출근하고, 저녁을 먹고 돌아오는 일상의 반복이다. 주말은 가족을 보러…

3주 ago

2024년 10월 6일 일요일 – 서울 생활 123주차

Planning A well-structured plan has the following characteristics:   First, the ultimate vision you aim to…

2개월 ago

2024년 9월 29일 일요일 – 서울 생활 122주차

English The most common problem for English learners like myself is that we often use…

2개월 ago

2024년 9월 22일 일요일 – 서울 생활 121주차

추석 추석을 맞아 친가 외가 처가 어르신들을 모두 뵙고 돌아왔다. 아이가 태어난지는 좀 됐지만 한국에서…

2개월 ago

2024년 9월 8일 일요일 – 서울 생활 119주차

주말 이번주는 아내가 올라와서 주말을 함께 보냈다. 둘만 밥도 먹고 뮤지컬도 보고, 모임도 나가고 집에서…

2개월 ago

This website uses cookies.