问题：
计算给定完全二叉树的节点个数。
Example:
Input:
1
/ 2 3
/ \ /
4 5 6
Output: 6
解法：Complete Binary Tree（完全二叉树）
首先明确以下定义：
因此这样的二叉树，也叫做 Full Binary Tree
本题中，
时间复杂度：
一般递归次数：树的高度 O(logN)
每次递归时间：（?? 优化 求树高花时间=树高）O(logN)
因此，总共花时间：O(logN*logN)
代码参考：
1 /** 2 * Definition for a binary tree node. 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode() : val(0), left(nullptr), right(nullptr) {} 8 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} 9 * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} 10 * }; 11 */ 12 class Solution { 13 public: 14 //recursion 15 //Def: return the count of node 16 // -> full binary tree -> 2^hight-1 17 // -> complete binary tree -> tofind left, right tree, recursionly. 18 //Status: root 19 //Opt: (after get left,right result) 20 // return left+right+1. 21 //base: 22 // root==null: return 0. 23 int countNodes(TreeNode* root) { 24 if(!root) return 0; 25 int lh = 1, rh = 1; 26 TreeNode* l = root->left; 27 while(l) { 28 lh++; 29 l = l->left; 30 } 31 TreeNode* r = root->right; 32 while(r) { 33 rh++; 34 r = r->right; 35 } 36 //full binary tree 37 if(lh==rh) { 38 return pow(2,lh)-1;//2^hight-1 39 } 40 //complete binary tree -> recursion 41 lh = countNodes(root->left); 42 rh = countNodes(root->right); 43 return lh+rh+1; 44 } 45 };
222. Count Complete Tree Nodes
原文：https://www.cnblogs.com/habibah-chang/p/13752794.html