给你一棵 完全二叉树 的根节点 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) 的简单解决方案。你可以设计一个更快的算法吗？
法一：直接递归模拟：
/**
* 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) {
int ans = 0;
findAns(root, ans);
return ans;
}
private:
void findAns(TreeNode *node, int &ans)
{
if (node == nullptr)
{
return;
}
++ans;
findAns(node->left, ans);
findAns(node->right, ans);
}
};
如果树中有n个节点，此算法时间复杂度为O(n)，空间复杂度为O(logn)。
法二：手动模拟一个栈，中序遍历：
/**
* 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) {
stack<TreeNode *> s;
s.push(root);
int ans = 0;
while (!s.empty())
{
TreeNode *curNode = s.top();
s.pop();
if (curNode)
{
++ans;
s.push(curNode->left);
s.push(curNode->right);
}
}
return ans;
}
};
如果树中有n个节点，此算法时间复杂度为O(n)，空间复杂度为O(logn)。
法三：Morris中序遍历：
/**
* 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) {
int ans = 0;
TreeNode *curNode = root;
while (curNode)
{
if (curNode->left == nullptr)
{
++ans;
curNode = curNode->right;
continue;
}
TreeNode *mostRightOfLeft = getMostRightOfLeft(curNode);
if (mostRightOfLeft->right == nullptr)
{
mostRightOfLeft->right = curNode;
curNode = curNode->left;
}
else if (mostRightOfLeft->right == curNode)
{
++ans;
mostRightOfLeft->right = nullptr;
curNode = curNode->right;
}
}
return ans;
}
private:
TreeNode *getMostRightOfLeft(TreeNode *node)
{
TreeNode *curNode = node->left;
while (curNode->right && curNode->right != node)
{
curNode = curNode->right;
}
return curNode;
}
};
如果树中有n个节点，此算法时间复杂度为O(n)，空间复杂度为O(1)。
法四：层序遍历：
/**
* 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) {
deque<TreeNode *> dq;
dq.push_back(root);
int ans = 0;
while (!dq.empty())
{
TreeNode *node = dq.front();
dq.pop_front();
if (node)
{
++ans;
if (node->left)
{
dq.push_back(node->left);
}
if (node->right)
{
dq.push_back(node->right);
}
}
}
return ans;
}
};
如果树中有n个节点，此算法时间复杂度为O(n)，空间复杂度为O(logn)。
法五：利用完全二叉树的特点，完全二叉树除了最后一层外，其他层都是满节点的，因此我们可以先计算出除最后一层外的所有层的节点数，然后利用二分法，找到最后一层的节点数：
/**
* 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;
}
int h = 0;
TreeNode *curNode = root;
while (curNode)
{
++h;
curNode = curNode->left;
}
int left = 0;
int right = (1 << (h - 1)) - 1;
int bottomNum = 0;
while (left <= right)
{
TreeNode *curNode = root;
int mid = (left + right) / 2;
for (int i = h - 2; i >= 0; --i)
{
if ((1 << i) & mid)
{
curNode = curNode->right;
}
else
{
curNode = curNode->left;
}
}
if (curNode == nullptr)
{
right = mid - 1;
}
else
{
bottomNum = mid;
left = mid + 1;
}
}
return pow(2, h - 1) + bottomNum;
}
};
如果树中有n个节点，此算法时间复杂度为O(lg 2 ^2 2n)，找出树的高度需要logn的时间，对于二分的外层循环需要logn的时间，每次二分查找需要logn的时间来确定是否有叶子节点；空间复杂度为O(1)。
