完全二叉树的节点个数 图解题解
这道题到底在问什么
- 输入
- 一棵 11 个节点的完全二叉树
- 输出
- 11
先想最直接的笨办法
递归结束：根节点自己 1 个，左子树是满树一次性数出 7 个，右子树是满树数出 3 个，合计 11 个。全程只递归了 3 层、量了几条高度，远少于挨个数 11 次。（动画第 28 步）
最优解：一步一步想明白
- 3记住这把钥匙：左高 hl、右高 hr。两者相等 → 这块是满树，套公式秒算；不等 → 自己算 1，再递归左右子树。
- 4先看清整棵树。我们从根节点 1 出发，先量它的左侧高度，再量右侧高度，靠这两个数判断要不要往下递归。
- 5递归来到节点 1（橙色）。要决定怎么处理它，先量两条高度：左高 hl 是从它只往左能走几层，右高 hr 是只往右能走几层。
- 6量左高 hl：从节点 1 出发只往左孩子走，走到节点 2，这是第 1 步。蓝色是已经走过的左脊。
- 7量左高 hl：从节点 1 出发只往左孩子走，走到节点 4，这是第 2 步。蓝色是已经走过的左脊。
- 8量左高 hl：从节点 1 出发只往左孩子走，走到节点 8，这是第 3 步。蓝色是已经走过的左脊。
- 9左脊到底，再往左没有孩子了。所以节点 1 的左高 hl = 3。接下来量右高。
- 10量右高 hr：从节点 1 出发只往右孩子走，走到节点 3，这是第 1 步（绿色是右脊）。
- 11量右高 hr：从节点 1 出发只往右孩子走，走到节点 7，这是第 2 步（绿色是右脊）。
- 12右脊也到底了，节点 1 的右高 hr = 2。现在两个高度都有了：hl = 3，hr = 2。
- 13hl != hr（3 ≠ 2），这块不是满树。那就老实点：把节点 1 自己算 1 个（标绿），然后分别递归去数它的左子树和右子树。
- 14递归来到节点 2（橙色）。要决定怎么处理它，先量两条高度：左高 hl 是从它只往左能走几层，右高 hr 是只往右能走几层。
- 15量左高 hl：从节点 2 出发只往左孩子走，走到节点 4，这是第 1 步。蓝色是已经走过的左脊。
- 16量左高 hl：从节点 2 出发只往左孩子走，走到节点 8，这是第 2 步。蓝色是已经走过的左脊。
- 17左脊到底，再往左没有孩子了。所以节点 2 的左高 hl = 2。接下来量右高。
- 18量右高 hr：从节点 2 出发只往右孩子走，走到节点 5，这是第 1 步（绿色是右脊）。
- 19量右高 hr：从节点 2 出发只往右孩子走，走到节点 11，这是第 2 步（绿色是右脊）。
- 20右脊也到底了，节点 2 的右高 hr = 2。现在两个高度都有了：hl = 2，hr = 2。
- 21hl == hr（都是 2）！说明以 2 为根的整块子树是满二叉树，节点数直接套公式 2^(2+1) − 1 = 7。绿色这一整块一次性数完，不用再往下递归。
- 22递归来到节点 3（橙色）。要决定怎么处理它，先量两条高度：左高 hl 是从它只往左能走几层，右高 hr 是只往右能走几层。
- 23量左高 hl：从节点 3 出发只往左孩子走，走到节点 6，这是第 1 步。蓝色是已经走过的左脊。
- 24左脊到底，再往左没有孩子了。所以节点 3 的左高 hl = 1。接下来量右高。
- 25量右高 hr：从节点 3 出发只往右孩子走，走到节点 7，这是第 1 步（绿色是右脊）。
- 26右脊也到底了，节点 3 的右高 hr = 1。现在两个高度都有了：hl = 1，hr = 1。
- 27hl == hr（都是 1）！说明以 3 为根的整块子树是满二叉树，节点数直接套公式 2^(1+1) − 1 = 3。绿色这一整块一次性数完，不用再往下递归。
- 28递归结束：根节点自己 1 个，左子树是满树一次性数出 7 个，右子树是满树数出 3 个，合计 11 个。全程只递归了 3 层、量了几条高度，远少于挨个数 11 次。
⚠️ 容易写错的地方
✗ 错：不管满不满都递归到底
✓ 对：先比 hl 和 hr，相等就直接套公式返回
不利用满树特性就退化成 O(n)，本题的优化点全在这一步
✗ 错：公式记成 2^h − 1（用了高度差 1 的值）
✓ 对：高度 h 指边数，满树节点数 = 2^(h+1) − 1
把「层数」和「边数」搞混会少算一整层，结果偏小一半
✗ 错：hl != hr 时忘了把当前节点自己算 1
✓ 对：return 1 + 左 + 右
只加左右子树会漏掉当前根节点，总数少 1
完整代码（Python / C++ / Java）
Python
def countNodes(root):
if not root:
return 0
hl = leftHeight(root) # 一路往左
hr = rightHeight(root) # 一路往右
if hl == hr: # 满树，套公式
return (1 << (hl + 1)) - 1
# 不等：自己 1 + 递归左右
return 1 + countNodes(root.left) + countNodes(root.right)
def leftHeight(node):
h = 0
while node.left:
node = node.left; h += 1
return hC++
int leftH(TreeNode* n){ int h=0; while(n->left){n=n->left;h++;} return h; }
int rightH(TreeNode* n){ int h=0; while(n->right){n=n->right;h++;} return h; }
int countNodes(TreeNode* root){
if(!root) return 0;
int hl = leftH(root), hr = rightH(root);
if(hl == hr) return (1 << (hl + 1)) - 1; // 满树
return 1 + countNodes(root->left) + countNodes(root->right);
}Java
int leftH(TreeNode n){ int h=0; while(n.left!=null){n=n.left;h++;} return h; }
int rightH(TreeNode n){ int h=0; while(n.right!=null){n=n.right;h++;} return h; }
public int countNodes(TreeNode root) {
if (root == null) return 0;
int hl = leftH(root), hr = rightH(root);
if (hl == hr) return (1 << (hl + 1)) - 1; // 满树
return 1 + countNodes(root.left) + countNodes(root.right);
}复杂度
时间
O(log²n)
递归最多 O(log n) 层，每层量左右高度各 O(log n)，相乘 O(log²n)，远快于 O(n)
空间
O(log n)
递归栈深度等于树高 O(log n)，没有额外大数组
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 完全二叉树的节点个数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么这个算法是 O(log²n) 而不是 O(log n)？+
递归 O(log n) 层，但每层都要重新量一次左高和右高，量高度本身是 O(log n)，所以两者相乘是 O(log²n)。
为什么递归层数只有 O(log n)，而不是把整棵树都递归一遍？+
每次 hl != hr 往下递归时，左右两棵子树里至少有一棵是满的、会被公式直接算掉，真正继续递归的那条路只沿着树的一侧下降，深度就是树高 O(log n)。
满二叉树的公式怎么来的？+
高度为 h（按边数算）的满二叉树有 h+1 层，第 k 层有 2^k 个节点，等比求和 1+2+…+2^h = 2^(h+1) − 1。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 完全二叉树的节点个数 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。