리트코드 - 222. Count Complete Tree Nodes

리트코드 - 222. Count Complete Tree Nodes

출처 - https://leetcode.com/problems/count-complete-tree-nodes/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

완전한 이진 트리의 루트가 주어지면 트리의 노드 수를 반환합니다.
Wikipedia에 따르면 마지막 레벨을 제외한 모든 레벨은 완전한 이진 트리로 완전히 채워지며 마지막 레벨의 모든 노드는 최대한 왼쪽에 있습니다.  마지막 레벨 h에 1~2h 노드가 포함될 수 있습니다.
 O(n) 시간 복잡도 미만으로 실행되는 알고리즘을 설계합니다.

 

의사코드

함수 countNodes     if (root =null)         0 리턴     1 + countNodes(root.left) + countNodes(root.right) 함수 끝

 

풀이코드

1. 재귀방식

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        } 
       
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}

2. Queue 사용방식 (BFS)

class Solution {
    public int countNodes(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();

        if (root == null) {
            return 0;
        }

        q.offer(root);
        int count = 0;

        while (!q.isEmpty()) {
            TreeNode cur = q.poll();
            count++;
            if (cur.left == null && cur.right == null) {
                continue;
	        }

            if (cur.left != null) {
                q.offer(cur.left);
            }

            if (cur.right != null) {
                q.offer(cur.right);
            }
        }
        
        return count;
    }
}

 

코드설명

재귀를 이용한 방식과 Queue를 이용한 방식 두가지 풀이가 있다.

첫번째 재귀를 이용한 방식은 재귀를 통해 자식 노드를 방문하여 null이 아닌 경우 1을 가지고 더하게끔 설계가 되어있다.

자식노드의 합을 가지고 있는 값들을 상위로 올라가면서 더해서 결과적으로 root에서 모든 노드의 수를 포함하고 있다.

 

두번째 queue를 이용한 방식은 root를 queue에 넣고 반복문을 돌린다.

queue에서 꺼낼때 count를 하고, 만약 leaf 노드 인 경우 넘어간다.

왼쪽 자식 노드가 null이 아니면 queue에 추가하고, 마찬가지로 오른쪽 자식 노드가 null이 아니면 queue에 추가한다.

FIFO에 의해 같은 레벨에 있는 왼쪽과 오른쪽을 모두 탐색한 후에, 다음 레벨 노드를 탐색하기 때문에 BFS가 된다.

 

두 방식의 차이는 첫번째는 런타임은 빠르지만 노드를 쌩(?)으로 사용하기 때문에 메모리를 많이 먹는다는 것이고

두번째는 런타임은 느리지만 메모리를 적게 잡아먹는다. 이것이 두 방식의 차이이다.

 

 

시간복잡도 - O(n)

공간복잡도 - O(n)

 

문제를 풀며 생각한 흐름과 배운 점

노드 문제는 이제 다소 쉬워진 것 같다.

조금 더 복잡한 문제를 풀어보는게 좋을 것 같다.

 

정리

정렬된 이진트리의 노드의 갯수를 세는 방법