[python3] 958. Check Completeness of a Binary Tree

풀이 일자: 23.03.15

난이도: [Medium]

분류: [BFS]

문제 내용

이진 트리의 root Node가 주어졌을 때, 해당 이진 트리가 완전이진트리 여부를 리턴하는 문제였다.

 

완전이진트리

- 마지막 level전까지는 모든 노드가 다 채워져있어야 하고 마지막 level은 굳이 다 채울 필요는 없지만 왼쪽부터 차례대로 채워야 한다.

 

문제 해결 흐름

1. 우선 같은 level에서 확인해야 하고 각 node를 확인하기 위해 알고리즘을 선택해야한다.

→ BFS를 채택하여 이를 해결한다.

 

2.  순회를 하면서 안되는 경우가 발생하면 바로 False를 리턴한다.

→ 1) 같은 부모노드를 갖는 자식노드 중 오른쪽 노드만 존재하는 경우 False

→ 2) slbling관계의 서로 붙어있는 부모노드 사이를 가정했을 때 왼쪽 부모노드의 right 노드가 존재하지 않지만 오른쪽 부모노드의 left노드가 존재하지 않는 경우 False

 

# 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 isCompleteTree(self, root: Optional[TreeNode]) -> bool:
        q = deque([[root,0]]);

        while(q):
            node, h = q.pop();
            if node.left == None and node.right:  # 같은 부모노드를 가지면서 왼쪽 노드만 없으면
                return False;
            else:
                if node.left:
                    q.appendleft([node.left, h+1]);
                if node.right:
                    q.appendleft([node.right,h+1]);
                else:
                    if q:                         # 오른쪽 노드가 없는 경우 바로 옆 서브트리의 왼쪽 노드가 있는 경우 False
                        node, h = q.pop();        # 꺼내서 확인만 하고 다시 넣기.
                        if node.left != None:
                            return False;
                        else:
                            q.append([node, h]);
        return True;

Time Complexity: O(N)

최악의 경우 Tree 내의 모든 원소를 순회해야하기 때문에 N의 시간복잡도를 가질 것이다.

 

Space Complexity: O(2^h)

공간복잡도는 맨 아래의 level의 leaf 노드의 갯수가 가장 클 것이므로 2^h의 공간복잡도를 가질 것이다. 

 

다른 해결 방식

1. 복잡하게 경우의 수를 생각하지 않고 어차피 queue에 차례대로 들어가는 것 이용

→ tree를 돌다가 None이 확인되면 다음으로 넘어가서 이전이 None인 경우가 있었는데 노드가 존재하면 False return

#Official Solution
class Solution:
    def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
        if root == None:
            return true;

        nullFound = False;
        q = deque([root]);

        while(q):
            node = q.pop();
            
            if (node == None):
                nullFound = True;
            else:
                if nullFound:
                    return False;
                q.appendleft(node.left);
                q.appendleft(node.right);
        return True;

Time Complexity: O(N)

최악의 경우 Tree 내의 모든 원소를 순회해야하기 때문에 N의 시간복잡도를 가질 것이다.

 

Space Complexity: O(2^h)

공간복잡도는 맨 아래의 level의 leaf 노드의 갯수가 가장 클 것이므로 2^h의 공간복잡도를 가질 것이다. 

 

 

2.  BFS로 되는 만큼 다른 순회 알고리즘인 DFS가 되겠다.

→  근데 굳이? 같은 level을 확인하는 것이 훨씬 유리하기 때문에 DFS는 부적합하긴 하다.

 

 

 

문제 링크

https://leetcode.com/problems/check-completeness-of-a-binary-tree/

Check Completeness of a Binary Tree - LeetCode