완전한 트리 노드 수 계산

2329 단어 javascriptleetcode
완전한 이진 트리의 루트가 주어지면 트리의 노드 수를 반환합니다.

Wikipedia에 따르면 마지막 레벨을 제외한 모든 레벨은 완전한 이진 트리로 완전히 채워져 있으며 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있습니다. 마지막 레벨 h에서 포함하여 1~2h 노드를 가질 수 있습니다.

O(n) 시간 복잡도 미만으로 실행되는 알고리즘을 설계합니다.

예 1:
입력: 루트 = [1,2,3,4,5,6]
출력: 6

/**
 * 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)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var countNodes = function(root) {
    let result = [];

    function inOrderTraversal(node){
        if(node === null){
            return null;
        }
        inOrderTraversal(node.left);
        result.push(node.val)
        inOrderTraversal(node.right);

    }
    inOrderTraversal(root);
    return result.length

};

좋은 웹페이지 즐겨찾기