打卡第二十天
3道简单题 (简单在哪里....二叉树咋这么难)
题目: 给你一棵完全二叉树的根节点root，求出该树的节点个数。
方法一: 递归:完全二叉树只有两种情况，一是满二叉树，二是最后一层叶子节点没有满。
对于情况一，用 2^树深度 - 1 来计算。
对于情况二，分别递归左子树和右子树，递归计算左子树节点数 + 右子树节点数 + 1。
代码:
class Solution {
public:int countNodes(TreeNode* root) {if (root == nullptr){return 0;}TreeNode* left = root->left;//左子树指针TreeNode* right = root->right;//右子树指针int leftDepth = 0, rightDepth = 0;//初始化左右子树深度为0while (left) { // 求左子树深度left = left->left;leftDepth++;}while (right) { // 求右子树深度right = right->right;rightDepth++;}if (leftDepth == rightDepth) {return (2 << leftDepth) - 1; // (2<<1) 相当于2^2，所以leftDepth初始为0}return countNodes(root->left) + countNodes(root->right) + 1;}
};
方法二: 二分查找+位运算
完全二叉树的最后一层节点编号是连续的,在 [2^level, 2^(level+1)-1] 范围内二分查找最后一个存在的节点
节点编号 k 的二进制表示（去掉最高位的1）就是从根节点到该节点的路径: 0 表示向左，1 表示向右
位运算实现逻辑:
代码:
class Solution {
public:int countNodes(TreeNode* root) {if (root == nullptr) {return 0;}// 计算树的高度int level = 0;TreeNode* node = root;while (node->left != nullptr) {level++;node = node->left;}// level层是最底层，节点编号从 2^level 到 2^(level+1)-1int low = 1 << level; // 最低可能节点编号：2^levelint high = (1 << (level + 1)) - 1; // 最高可能节点编号：2^(level+1)-1// 二分查找：在[low, high]范围内找到最后一个存在的节点编号while (low < high) {int mid = (high - low + 1) / 2 + low; // 向上取整，避免死循环if (exists(root, level, mid)) {low = mid; // mid存在，说明最终答案 >= mid} else {high = mid - 1; // mid不存在，说明最终答案 < mid}}return low; // 此时low == high，就是节点总数}// 判断编号为k的节点是否存在bool exists(TreeNode* root, int level, int k) {int bits = 1 << (level - 1); // 用于位运算的掩码TreeNode* node = root;// 根据k的二进制表示从高位到低位遍历路径while (node != nullptr && bits > 0) {if (!(bits & k)) { // 当前位为0，往左走node = node->left;} else { // 当前位为1，往右走node = node->right;}bits >>= 1; // 移到下一位}return node != nullptr; // 如果node不为空，说明该节点存在}
};
int bits = 1 << (level - 1); // 用于位运算的掩码
耗时≈两小时 明天继续