题目

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

输入： root = [1,2,3,4,5,6]
输出： 6

题解

第一种

我们在函数中先判断root是否为空，如果是那么我们直接返回0，然后我们声明了两个变量h1和h2，并将其设置为0，然后我们声明了两个指针l和r，并将它们都指向根节点，接下来我们使用循环去计算左子树的高度，在循环中，我们将指针l不断地指向左子节点，每次循环h1的值加1，直到l为空，这样h1的值就代表了左子树的高度，然后我们使用另一个循环来计算右子树的高度，在循环中，我们将指针r不断地指向右子节点，每次循环h2的值加1，直到r为空，这样h2的值就代表了右子树的高度，然后我们使用条件判断来比较左右子树的高度h1和h2是否相等，如果相等则说明该二叉树是一棵满二叉树，我们直接返回这个值即可，如果左右子树的高度不相等则说明该二叉树不是满二叉树，我们这里需要递归地计算左子树和右子树的节点数量，将它们相加后再加上根节点本身，最后返回这个值即可

var countNodes = function(root) {
    if(!root) return 0
    let h1 = 0, h2 = 0
    let l = root, r = root
    while(l) {
        l = l.left
        h1++
    }
    while(r) {
        r = r.right
        h2++
    }
    if(h1===h2) return Math.pow(2, h1)-1
    return countNodes(root.left)+countNodes(root.right)+1
};

第二种

我们在函数中先判断root是不是空，如果是则直接返回0，然后我们声明了一个空数组que，用于存储待处理的节点，然后我们将根节点root推入数组que中，接下来我们声明了一个变量result，用于记录节点数量，将值初始化为0， 然后我们使用循环去遍历数组que，直到数组为空为止，在循环中，我们首先获取当前数组que的长度，存储在变量size中，然后我们使用循环去遍历当前层级的节点，在循环中，我们从数组que的头部取出一个节点，赋值给变量node，并将节点数量result加1，然后我们去判断当前节点是否有左子节点和右子节点，如果有左子节点，我们则将左子节点推入数组que中，如果有右子节点，我们将右子节点推入数组que中，这样我们就完成了对当前层级节点的处理，同时将下一层级的节点推入数组que中，当数组que为空时，则说明我们已经遍历了所有节点，这个时候我们返回节点数量result即可

var countNodes = function(root) {
    if (!root) return 0;
    const que = [];
    que.push(root);
    let result = 0;
    while (que.length){
        const size = que.length;
        for (let i=0; i<size; i++){
            node = que.shift();
            result++;
            node.left && que.push(node.left);
            node.right && que.push(node.right);
        }
    }
    return result;
}