https://leetcode.cn/problems/count-complete-tree-nodes/description/
一、题目解析
给定一棵完全二叉树，统计节点个数。普通做法是 O(n) 遍历整棵树，但完全二叉树有结构特性可以利用——很多子树本身就是满二叉树，不需要遍历就可以直接用公式 2^h - 1 算出节点数（h 为层数）。
以这棵完全二叉树为例，左子树深度 = 右子树深度，它是满二叉树：
plain text
1 / \ 2 3 / \ / 4 5 6左侧深度（沿 left 链到底）为 3，右侧深度（沿 right 链到底）为 2。左右深度不等，说明不是满二叉树，递归处理。但它的左子树 [2,4,5] 左侧深度 = 右侧深度 = 2，是满二叉树，直接返回 2² - 1 = 3。
二、核心思路：满二叉树剪枝
对每个子树做两步判断：
- 沿
left链走到底，得左侧深度 l - 沿
right链走到底，得右侧深度 r
如果 l == r，说明这棵子树是满二叉树，节点数 = 2^l - 1，直接返回，不再递归（剪枝）。
如果 l != r，说明最后一层没填满，按普通方式递归：countNodes(left) + countNodes(right) + 1。
关键点：对一个完全二叉树，左右深度至多差 1。如果左侧更深，说明右子树是满的（比左子树少一层）；如果两侧相等，整个子树都是满的。因此每次递归至少有一侧可以剪枝——复杂度降到 O(log²n)。
三、代码实现
java
class Solution { public int countNodes(TreeNode root) { // 空树 if (root == null) { return 0; } // 计算左侧深度：沿 left 链走到底 int l = 1; TreeNode left = root.left; while (left != null) { left = left.left; l++; } // 计算右侧深度：沿 right 链走到底 int r = 1; TreeNode right = root.right; while (right != null) { right = right.right; r++; } // 左右深度相等 → 满二叉树，公式直接算 if (l == r) { return (int) Math.pow(2, l) - 1; } // 不是满二叉树 → 递归，左右子树至少一侧可剪枝 return countNodes(root.left) + countNodes(root.right) + 1; }}时间复杂度 O(log²n)：每次递归 O(log n) 算深度，树高 O(log n)，最坏每层递归一次。
空间复杂度 O(log n)，递归栈深度。
本文由 AgentPlanFlow 生成