leetcode之Count Complete Tree Nodes

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 = 0;
    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

看样子效率是个问题啊。从完全二叉树的特性上入手再试试。

leetcode之Count Complete Tree Nodes

原文：http://www.cnblogs.com/liu-binq63/p/4568006.html