好的外贸网站的特征/seo小白入门

题目

OJ平台

解题分析

• 如果仅仅不去利用性质做题的话，很简单！

具体实现没啥好说的。

int countNodes(struct TreeNode* root){if(!root)return 0;return countNodes(root->left)+countNodes(root->right)+1;
}

• 利用完全二叉树的性质

这题实在太妙了，将位运算和完全二叉树完美结合

1. 根据完全二叉树的性质，确认出该完全二叉树可能的结点个数范围(求深度可用最左子树的深度来求)
2. 根据这个范围进行二分
3. 判断这个完全二叉树是否具有 k 个节点的方式：根据编号的二进制表示规律来进行
   编号的二进制表示规律：

• 在第几层编号就是这么多个数据位，如在第二层的编号为2和3对应10，11。
• 且最高位必定是1。
• 一个**结点的左孩子的编号就是它父孩子编号然后在后面+0，右孩子编号就是在后面+1。**如编号1的左右孩子为10和11。

解题代码

C语言实现

typedef struct TreeNode TreeNode;bool check(TreeNode *root, int level, int k) {int idx = 1 << (level - 1);struct TreeNode *node = root;while (node != NULL && idx > 0) {//以k为地图，进行下一个的走向，如果最终的终点不是NULL则至少是右k个节点//举个例子110的序列，则第一个开始序列应该是1，即第一次往右，第二个是0，则往左，所以idx初始化为(1<<level-1)if ((idx) & k) {  //该层选择了1，故选择了右孩子node = node->right;} else {node = node->left;}idx >>= 1;}return node != NULL;
}int countNodes(struct TreeNode *root) {if (!root)return 0;int level = 0;TreeNode *node = root;while (node->left) {level++;node = node->left;}if (!level)return 1;int left = 1 << level, right = 1 << (level + 1);while (left < right) {int mid = (left + right) / 2;if (check(root, level, mid)) {  //至少是有mid个，所以寻找右边界的二分left = mid + 1;} else {right = mid;}}return left - 1;
}