222.完全二叉树节点个数

节点个数"/>

222.完全二叉树节点个数

​​题目来源：

        leetcode题目，网址：222. 完全二叉树的节点个数 - 力扣（LeetCode）

解题思路：

       遍历计数即可。

解题代码：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int countNodes(TreeNode* root) {if(root==nullptr){return 0;}queue<TreeNode*> q1;q1.push(root);int res=1;while(q1.size()!=0){TreeNode* temp=q1.front();q1.pop();if(temp->left!=nullptr){q1.push(temp->left);res++;}if(temp->right!=nullptr){q1.push(temp->right);res++;}}return res;}
};

总结：

        时间复杂度是 O(n)，但没有用到完全二叉树的性质。

        官方题解是二分查找+位运算。假设完全二叉树有 k 层，则其节点个数范围是 [2^k,2^(k+1)-1]。二分查找时，节点从根节点开始，数从二进制第二位开始，若该位为 1，移动到该节点的右节点上，否则移动到该节点的左节点上。