完全二叉树的节点个数

落日映苍穹つ 2022-12-23 09:44 172阅读 0赞

> leetcode 222 题 \[medium\]  
> 中：[完全二叉树的节点个数][Link 1]  
> 英：[Count Complete Tree Nodes][]  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKMTU1MQ_size_16_color_FFFFFF_t_70_pic_center]

##### 题解一： #####

> 使用DFS或BFS可以直接简单的解决这道题

1.  实现：DFS + 优化（提前结束递归）
    
        /** * 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) { 
            /** * DFS + 优化 * 时间复杂度：O(n) + 优化 * 空间复杂度: O(logn) 递归栈空间 */
            // 预处理
            if(!root) return 0;
            
            // 计算树高（完全二叉树，一直找左子节点，一定能到达最后一层）
            let height = 1;			// 树高度
            let node = root;
            while(node = node.left) height++;
            
            // DFS
            let bottomCount = 0;	// 统计最后一层的结点数
            let canStop = false; 	// 优化：当查询到最后一层结束，canStop设置为true，表明后续的递归无需再进行
            function recurse(_root, _currHeight = 1){ 
                if(canStop) return;			// 结果已获得，递归可以结束了
                // 后续遍历
                _root.left && recurse(_root.left, 1 + _currHeight);
                _root.right && recurse(_root.right, 1 + _currHeight);
                if(_currHeight === height){  // 当前是最后一层
                    bottomCount++;
                }
                else if(!_root.left && !_root.right){  // 不是最后一层，但碰到叶子节点了，说明最后一层的结点数量统计结束
                    canStop = true;
                }
            }
            recurse(root);	// 执行DFS
            
            // 计算结果
            let result = bottomCount;
            for(let i=0; i<height-1; i++){ 
                result += Math.pow(2, i);
            }
            return result;
        };

##### 题解二： #####

> 利用完全二叉树的结构，使用 **二分查找** \+ **位运算**
> 
> 1.  **树高度**：从根开始一直查找左子节点，一定可以到达最后一层
> 2.  **二分查找**：结合结点的编码，最后一层的编码范围为 \[2^(height-1), 2^height - 1\] ，在最后一层中查找存在的最大的编码值即可
> 3.  **位运算**：实现 `exists` 函数，实现查找某一层中某个编码的结点是否存在（结合编码的二进制值以及位运算来判断）  
>     ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKMTU1MQ_size_16_color_FFFFFF_t_70_pic_center 1][]
> 
>  *  **查找6号结点是否存在**：6的二进制编码是 `110` ，二进制编码的后两位 `10` 可以确定该结点从根节点开始的查找路径
>  *  **位探针**：例如探针 `1000` 可以探查出某个二进制数右起第4位是0还是1（`!!(1000 & 1111) === true`，`!!(1000 & 0111) === false`）

1.  实现
    
        /** * 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) { 
            /** * 二分查找 + 位运算 * 时间复杂度：O((logn)² ) logn(exists) * log(n/2)(最后一层进行二分查找)) => (logn)² * 空间复杂度：O(1) */
            // 预处理
            if(!root) return 0;
            if(!root.left && !root.right) return 1;
            
            // 计算树高度
            let height = 1, currRoot = root;
            while(currRoot = currRoot.left) height++;
        
            // 辅助函数
            function exists(_i, _level){ 
                /** * 判断编码为_i的结点在树的_level层中是否存在。根节点编码为1。 * @param { Number } _i: 结点的编码 * @param { Number } _level: 查找的层数 * @return { Boolean }: 树中是否有该结点 */
                let currBit = 1 << (_level - 2);	// 初始化位探针，结合 & 运算符可以探查出出对应位是0还是1
                let node = root;
                while(currBit !== 0){ 
                    if(currBit & _i){    // 非0，查询右孩子
                        node = node.right;
                    }
                    else{ 	// 0，查询左孩子
                        node = node.left;
                    }
                    currBit >>= 1;		// 位探针右移，下次探查路径的下一位
                }
                return !!node;
            }
        
            // 对最后一层进行二分查找：最后一层的结点编码范围为 [2^(height-1), 2^height - 1]
            let l = Math.pow(2, height - 1);
            let r = Math.pow(2, height) - 1;
            let result = 0;
            while(l <= r){ 
                let mid = l + Math.floor((r - l) / 2);
                if(exists(mid, height)){     // 中点存在
                    result = mid;
                    l = mid + 1;
                }
                else{ 
                    r = mid - 1;
                }
            }
            return result;
        };

[Link 1]: https://leetcode-cn.com/problems/count-complete-tree-nodes/
[Count Complete Tree Nodes]: https://leetcode.com/problems/count-complete-tree-nodes/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKMTU1MQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/2a497541109248b491c96e29ebf428c5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKMTU1MQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/c73bd9cf521e4c7c9a04d83b51304032.png