Given a complete binary tree, count the number of nodes.
Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2hnodes inclusive at the last level h.
计算一个完全二叉树的所有节点。
我看到“二叉树”和“所有节点”两个关键词后，立即想到用递归的方法解决，于是就有了下面的代码。
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
int countNodes(struct TreeNode* root) {
int count = ;
if (!root){
return count;
}
if (root->left){
count += countNodes(root->left);
}
if (root->right){
count += countNodes(root->right);
}
return count;
}
提交之后，出现错误：
Last executed input:Special Judge: very large tree
看样子效率是个问题啊。从完全二叉树的特性上入手再试试。