力扣-二叉树-222 完全二叉树节点的数量

思路1

利用层序遍历所有节点即可

代码1

class Solution {
public:int countNodes(TreeNode* root) {if(root == nullptr) return 0;queue<TreeNode*> que;que.push(root);int size = 0;while(!que.empty()){size += que.size();int length = que.size();while(length--){TreeNode* cur = que.front();que.pop();if(cur->left) que.push(cur->left);if(cur->right) que.push(cur->right);}}return size;}
};

思路2

完全二叉树一路向左和一路向右如果深度相同， 那就变成了一颗满二叉树，满二叉树有定义可以计算

代码2

class Solution {
public:int countNodes(TreeNode* root) {if(root == nullptr) return 0;int leftDepth = 0, rightDepth = 0;TreeNode* left = root->left,  *right = root->right;while(left){leftDepth++;left = left->left;}while(right){rightDepth++;right = right->right;}if(leftDepth == rightDepth) return (2<<leftDepth) - 1;return 1 + countNodes(root->left) + countNodes(root->right);}
};