题目描述

Given a complete binary tree, count the number of nodes.

Note:

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 2h nodes inclusive at the last level h.

样例

Example:

Input: 
    1
   / \
  2   3
 / \  /
4  5 6

Output: 6

算法1

(dfs) $O(n)$

找到当前节点左子树和右子树的leftheight与rightheight，如果相等返回2^h-1,否则返回1+左子树个数+右子树个数

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    int countNodes(TreeNode* root) {
        TreeNode *p=root, *q=root;
        int hl=0, hr=0;
        while(p)
        {
            hl++;
            p=p->left;
        }
        while(q)
        {
            hr++;
            q=q->right;
        }
        if(hl==hr)
            return pow(2, hl)-1;
        return 1+countNodes(root->left)+countNodes(root->right);
    }
};