[Leetcode] 222. Count Complete Tree Nodes - JS

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

 

1. 문제 분석

문제분석
--------------------
이진트리의 root가 주어질 때, 트리 속 노드의 갯수를 반환하라.
O(n) 시간복잡도 미만으로 풀어라.

제한조건
--------------------
- 트리 속의 노드 갯수는 0 ~ 5*10^4이다.
- 0 <= Node.val <= 5 * 10^4

 

2. 접근 방법

접근방법
--------------------
재귀함수로 left, right를 방문하여 node가 존재하면 외부 변수 count를 추가한다.

 

 

3. 코드

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
var countNodes = function(root) {
    if (!root) {
        return 0;
    }
    let count = 0;

    function helper(node) {
        if (!node) {
            return null;
        }
        count++;
        helper(node.left);
        helper(node.right);
    }
    
    helper(root);

    return count;
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n) 

- 공간복잡도: O(1)

 

root 노드의 왼쪽, 오른쪽 노드를 재귀함수로 호출하면서 자식 노드가 존재하면 외부 변수 count에 값을 추가하여 갯수를 반환한다.