[Easy] LeetCode - no.222 Count Complete Tree Nodes : Java

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

 

 

문제

완전 이진 트리의 root가 주어졌을 때, 이 트리의 노드의 개수를 반환할 것

 

Example 1

 

 

 

Input: root = [1,2,3,4,5,6]
Output: 6

 

 

 

 

 

 

풀이

    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }

        return countNodes(root.left) + countNodes(root.right) + 1;
    }

• root가 null이라면 리프 노드를 넘어선 것이니 카운트 X (0 반환)
• 재귀 호출 : 왼쪽 서브트리의 노드 개수 + 오른쪽 서브트리의 노드 개수 + 현재 노드를 카운팅하기 위한 1
• 시간복잡도 : O(N)