完全二叉树的节点个数
这道题我们先用普通二叉树来做这道题。那普通二叉树求节点个数，无非就是递归或者是迭代。
递归和我们前面讲的二叉树的最大深度类似，而迭代即与我们前面讲的二叉树的最大深度代码极为相似，只需要改一点就行.
递归
根据递归三部曲就行.
1.确定递归函数的参数和返回值:参数就是传入树的根节点，返回就返回以该节点为根节点二叉树的节点数量，所以返回值为int类型。
int _countNodes(TreeNode* root)
2.确定单层循环逻辑: 先求它的左子树的节点数量，再求的右子树的节点数量，最后取总和再加一 （加1是因为算上当前中间节点）就是目前节点为根节点的节点数量。
int leftnum=_countNodes(root->left); int rightnum=_countNodes(root->right); int treenum=leftnum+rightnum+1; return treenum;
3.确定结束条件:
1. if(root==nullptr) 2. { 3. return 0; 4. }
代码:
class Solution { public: int countNodes(TreeNode* root) { if(root==nullptr) { return 0; } int left=countNodes(root->left); int right=countNodes(root->right); return left+right+1; } };
迭代
前面有讲过层序遍历的模板，大家可以去看一下,这里我直接上代码
代码:
class Solution { public: int countNodes(TreeNode* root) { if(root==nullptr) { return 0; } queue<TreeNode*> q; q.push(root); int result=0; while(!q.empty()) { int size=q.size(); for(int i=0;i<size;i++) { TreeNode* node=q.front(); q.pop(); result++; if(node->left) q.push(node->left); if(node->right) q.push(node->right); } } return result; } };
我们来看下上面的代码时间复杂度和空间复杂度:
递归:
- 时间复杂度：O(n)
- 空间复杂度：O(log n)
迭代:
- 时间复杂度：O(n)
- 空间复杂度：O(n)
那我们可不可以用完全二叉树的特性来优化时间复杂度囊？
优化做法
完全二叉树比普通二叉树特殊，但又没有满二叉树那么特殊，计算它的节点总数，可以说是普通二叉树和满的结合版，先看代码：
如果是一个普通二叉树，显然只要向下面这样遍历一边即可，时间复杂度 O(N)：
int countNodes(TreeNode* root) { return 1+countNodes(root->left)+countNode(root->right); }
那如果是一棵满二叉树，节点总数就和树的高度呈指数关系：
int countNodes(TreeNode* root) { int h = 0; // 计算树的高度 while (root != null) { root = root.left; h++; } // 节点总数就是 2^h - 1 return (int)Math.pow(2, h) - 1; }
代码:
class Solution { public: int countNodes(TreeNode* root) { if(root==nullptr) { return 0; } TreeNode* l=root; TreeNode* r=root; //记录左右子树高度 int h1=0,h2=0; while(l!=nullptr) { l=l->left; h1++; } while(r!=nullptr) { r=r->right; h2++; } //如果左右子树的高度相同,则是一颗满二叉树 if(h1==h2) { return (int)pow(2, h1) - 1; } //如果高度不同则按照普通二叉树计算 return countNodes(root->left)+countNodes(root->right)+1; } };
- 时间复杂度：O(log n × log n)
- 空间复杂度：O(log n)
所以说，「完全二叉树」这个概念还是有它存在的原因的，不仅适用于数组实现二叉堆，而且连计算节点总数这种看起来简单的操作都有高效的算法实现。
