222. 完全二叉树的节点个数（JS实现）

柔情只为你懂 2022-11-26 09:52 156阅读 0赞

## 1 题目 ##

> 给出一个完全二叉树，求出该树的节点个数。  
> 说明：  
> 完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。  
> 示例:  
> 输入:  
> 1  
> /  
> 2 3  
> / \\ /  
> 4 5 6  
> 输出: 6

## 2 思路 ##

**这道题我是层序遍历整个树，统计了一遍节点数量，没有用到完全二叉树这个概念，由于是完全二叉树，则除去最后一层的节点数量为`2^d - 1`，我们只需要计算完全二叉树最后一层有多少节点，可以给最后一层的节点编号`0...2^d - 1`，然后用二分算法来加快搜索速率：  
1.如果树为空，返回 0。  
2.计算树的高度 d(不包含最后一层)。  
3.如果 d == 0，返回 1。  
4.除最后一层以外的所有节点数为 2^d-1。最后一层的节点数通过二分搜索，检查最后一层有多少个节点。使用函数 exists(idx, d, root) 检查第 idx 节点是否存在。  
5.使用二分搜索实现 exists(idx, d, root)。  
6.返回 2^d - 1 + 最后一层的节点数**

## 3代码 ##

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */
    /** * @param {TreeNode} root * @return {number} */
    var countNodes = function(root) { 
        if (!root) return 0;
        const queqe = [root];
    
        let index = 0;
        while(queqe.length > 0) { 
            let p = queqe.shift();
            index++;
            if (p.left) queqe.push(p.left);
            if (p.right) queqe.push(p.right);
        }
    
        return index;
    };