难度中等892收藏分享切换为英文接收动态反馈
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
示例 1：
输入：root = [1,2,3,4,5,6]
输出：6示例 2：
输入：root = []
输出：0示例 3：
输入：root = [1]
输出：1提示：
- 树中节点的数目范围是
[0, 5 * 104] 0 <= Node.val <= 5 * 104- 题目数据保证输入的树是 完全二叉树
**进阶：**遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？
解题思路：
这道题不是简简单单的去遍历每个节点统计个数就行，因为这样子时间复杂度是 O(n)，也是因为我们没有利用完全二叉树的性质！
所以我们要换一下思路，因为我们都知道，完全二叉树就是最底层的叶子节点必须要连续，也就是说叶子节点以上层数的节点都是类似满树的，所以我们可以这样子想：
求树的节点个数，转化为求其左右子树的结点个数，而我们还能利用的是其前部分叶子结点是连续的性质，可以看到其有些子树是可以看作满子树的！也就是可以利用 来得到，而如果不是满子树的话，我们可以继续递归到该节点的左右子树，直到其结点的这部分子树是满子树为止！
而为了判断其是否为满树，我们可以分别从该结点往下，求其最左侧这条路径和最右侧这条路径的高度是否一致，一致则说明就是满树！
这样子算下来时间复杂度只有 O(logN * logN)，也就是求左右子树高度和递归的时候需要的时间复杂度！
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;
while(left != nullptr) // 计算左子树的深度
{
left = left->left;
leftDepth++;
}
while(right != nullptr) // 计算右子树的深度
{
right = right->right;
rightDepth++;
}
// 判断是否为满树，是的话利用满树节点个数特性直接返回
if(leftDepth == rightDepth)
return (2 << leftDepth) - 1;
// 不是满树则继续递归其左右子树直到遇到满树为止
return countNodes(root->left) + countNodes(root->right) + 1;
}
};