完全二叉树的节点个数

记住这把钥匙：左高 hl、右高 hr。两者相等 → 这块是满树，套公式秒算；不等 → 自己算 1，再递归左右子树。

先看清整棵树。我们从根节点 1 出发，先量它的左侧高度，再量右侧高度，靠这两个数判断要不要往下递归。

递归来到节点 1（橙色）。要决定怎么处理它，先量两条高度：左高 hl 是从它只往左能走几层，右高 hr 是只往右能走几层。

量左高 hl：从节点 1 出发只往左孩子走，走到节点 2，这是第 1 步。蓝色是已经走过的左脊。

量左高 hl：从节点 1 出发只往左孩子走，走到节点 4，这是第 2 步。蓝色是已经走过的左脊。

量左高 hl：从节点 1 出发只往左孩子走，走到节点 8，这是第 3 步。蓝色是已经走过的左脊。

左脊到底，再往左没有孩子了。所以节点 1 的左高 hl = 3。接下来量右高。

量右高 hr：从节点 1 出发只往右孩子走，走到节点 3，这是第 1 步（绿色是右脊）。

量右高 hr：从节点 1 出发只往右孩子走，走到节点 7，这是第 2 步（绿色是右脊）。

右脊也到底了，节点 1 的右高 hr = 2。现在两个高度都有了：hl = 3，hr = 2。

hl != hr（3 ≠ 2），这块不是满树。那就老实点：把节点 1 自己算 1 个（标绿），然后分别递归去数它的左子树和右子树。

递归来到节点 2（橙色）。要决定怎么处理它，先量两条高度：左高 hl 是从它只往左能走几层，右高 hr 是只往右能走几层。

量左高 hl：从节点 2 出发只往左孩子走，走到节点 4，这是第 1 步。蓝色是已经走过的左脊。

量左高 hl：从节点 2 出发只往左孩子走，走到节点 8，这是第 2 步。蓝色是已经走过的左脊。

左脊到底，再往左没有孩子了。所以节点 2 的左高 hl = 2。接下来量右高。

量右高 hr：从节点 2 出发只往右孩子走，走到节点 5，这是第 1 步（绿色是右脊）。

量右高 hr：从节点 2 出发只往右孩子走，走到节点 11，这是第 2 步（绿色是右脊）。

右脊也到底了，节点 2 的右高 hr = 2。现在两个高度都有了：hl = 2，hr = 2。

hl == hr（都是 2）！说明以 2 为根的整块子树是满二叉树，节点数直接套公式 2^(2+1) − 1 = 7。绿色这一整块一次性数完，不用再往下递归。

递归来到节点 3（橙色）。要决定怎么处理它，先量两条高度：左高 hl 是从它只往左能走几层，右高 hr 是只往右能走几层。

量左高 hl：从节点 3 出发只往左孩子走，走到节点 6，这是第 1 步。蓝色是已经走过的左脊。

左脊到底，再往左没有孩子了。所以节点 3 的左高 hl = 1。接下来量右高。

量右高 hr：从节点 3 出发只往右孩子走，走到节点 7，这是第 1 步（绿色是右脊）。

右脊也到底了，节点 3 的右高 hr = 1。现在两个高度都有了：hl = 1，hr = 1。

hl == hr（都是 1）！说明以 3 为根的整块子树是满二叉树，节点数直接套公式 2^(1+1) − 1 = 3。绿色这一整块一次性数完，不用再往下递归。

递归结束：根节点自己 1 个，左子树是满树一次性数出 7 个，右子树是满树数出 3 个，合计 11 个。全程只递归了 3 层、量了几条高度，远少于挨个数 11 次。

三个高频追问：复杂度为何带平方、为何只递归一条边、满树公式的由来。