Subscribe to see which companies asked this question.
完全二叉树。思路是先找到树的高度h，如果右子树的高度为h-1的话证明最后一个节点在右子树，左子树为满树，因此res+=左子树的节点个数+根节点=2^(h-1)，根节点移到右边。
如果右子树的高度不为h-1的话证明最后一个节点在左子树，右子树为满树，res+=右子树的节点个数+根节点=2^(h-2).根节点移到左边。
class Solution { public: int height(TreeNode* root){ return root==NULL ? -1 : height(root->left)+1; } int countNodes(TreeNode* root) { int sum=0, h=height(root); while(root){ if(height(root->right) == h - 1){ sum += pow(2,h); root = root->right; } else{ sum += pow(2,h-1); root = root->left; } h--; } return sum; } };需要注意的是这里为了计算方便，直接返回的h值就是实际的h值-1.比如叶子节点的高度是0.