一个不足20人的公司给你开出2万月薪，你敢入职吗?

刚看到个贴子，说一家不到20人的小公司给你开2万月薪，你敢不敢去。

从我的角度看，薪水给到位当然诱人，但关键还是看业务是否靠谱、现金流稳不稳。小公司给高薪，有可能是急缺关键岗位，也可能是没人敢来，你成了救火队。就像买菜一样，价格太离谱不是赚到，是得想想有没有坑。

换个角度想，职场本来就是风险和收益的组合。有经验的网友说得对：别光盯着工资，看老板、看产品、看财务状况，这些比人数更关键。敢不敢去不是问题，能不能稳才是重点。

总的来说还是量力而行，认清性价比。【备注:文末可领最新资料】

面试题：完全二叉树的节点个数

我们先把题目翻成大白话：

给你一棵完全二叉树，让你算这棵树有多少个节点，用 Python 实现算法。

听起来很普通对吧，但这题其实是面试里常见的“简单题里藏点小心机”。

先弄清楚：啥是“完全二叉树”？

别上来就写代码，先搞清楚树长啥样。

完全二叉树有两个关键点：

1. 除了最后一层，前面每一层节点都是满的
2. 最后一层的节点都尽量往左边挤

也就是说，它长得“很整齐”，不会出现这种诡异结构：左边空一块右边突然冒出个节点。

为什么要强调这个？ 因为这份“整齐”，刚好可以帮我们少算很多节点，甚至不用一个个数。

最直接但不聪明的写法：老老实实遍历

如果不利用“完全”的性质，就当普通二叉树来做，最简单的思路就是：

• 空节点：0 个
• 非空节点：左子树节点数 + 右子树节点数 + 自己这个 1

也就是一个经典递归：

classTreeNode:
def__init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


defcount_nodes_traverse(root: TreeNode) -> int:
ifnot root:
return0
return1 + count_nodes_traverse(root.left) + count_nodes_traverse(root.right)

这个复杂度是 **O(n)**，节点多少你就干多少活。 在普通二叉树里没问题，但题目特意说了“完全二叉树”，面试官肯定是想让你用这个条件优化一下。

利用完全二叉树特性：不遍历也能算出来一大块

重点来了。

对完全二叉树，有一个很好用的小性质：

从根出发一直往左走，走到头，得到一条“最左链”； 从根出发一直往右走，走到头，得到一条“最右链”。 如果两条链的长度相同，那这棵树其实是个满二叉树。

满二叉树的节点数有直接公式： 高度为 h（根节点高度算 1），节点数 = 2^h - 1

也就是说，如果当前这棵树刚好是满的，我们根本不用往下遍历，直接一行公式干完。

那如果最左高度 ≠ 最右高度呢？ 说明这棵树不是满的，只是完全二叉树，那就只能继续往下拆：

• 总节点数 = 1（根） + 左子树节点数 + 右子树节点数
• 左右子树本身也是完全二叉树，所以又可以继续用同一套逻辑算

于是就有了一个递归思路：

1. 计算当前子树的最左高度 lh
2. 计算当前子树的最右高度 rh
3. 如果 lh == rh：直接返回 (1 << lh) - 1
4. 否则：返回 1 + 左子树节点数 + 右子树节点数，并递归

classTreeNode:
def__init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


defcount_nodes(root: TreeNode) -> int:
# 主函数：统计完全二叉树的节点个数
ifnot root:
return0

# 计算最左边的高度
defleft_height(node: TreeNode) -> int:
        h = 0
while node:
            h += 1
            node = node.left
return h

# 计算最右边的高度
defright_height(node: TreeNode) -> int:
        h = 0
while node:
            h += 1
            node = node.right
return h

    lh = left_height(root)
    rh = right_height(root)

if lh == rh:
# 满二叉树，直接用公式 2^h - 1
return (1 << lh) - 1

# 不是满的，那就递归算左右子树，再加上根节点
return1 + count_nodes(root.left) + count_nodes(root.right)

看起来代码不长，但里面藏着几个点：

• left_height 和 right_height 都是一路走到底，复杂度是 O(树高)
• 完全二叉树高度大概是 log n
• 每一层我们会算一次高度，然后递归到下一层
• 综合下来时间复杂度大概是 **O((log n)^2)**，比 O(n) 好多了，特别是节点非常多的时候

顺便聊聊边界情况

几个常见的情况顺手说一下：

• root 是 None：直接返回 0，代码里一开始就处理了

• 只有一个节点：

• left_height 和 right_height 都是 1
• 直接按满二叉树算：2^1 - 1 = 1

• 左子树是满的，右子树不满（或反过来）：

• lh != rh，走递归那条分支
• 左、右子树仍然是完全二叉树，递归继续发挥作用

你会发现，这个算法完全没用到“数组下标存树”那一套，纯指针结构也好用。

整题核心就三句话：

1. 完全二叉树 + 最左高度 == 最右高度 ⇒ 这棵子树是满的
2. 满二叉树节点数有公式 2^h - 1
3. 否则就递归算左右子树：1 + left + right

记住这个套路，遇到“完全二叉树相关”的面试题，基本都能举一反三。 如果你在刷题平台上写，可以两个版本都写一下： 一个是朴素版遍历，一个是利用高度的高效版，对比下性能，会更有感觉。