【LeetCode刷题日记】222.极速计算完全二叉树节点数：O(log²n)算法揭秘

个人主页北极的代码欢迎来访作者简介java后端学习者❄️个人专栏苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言大家好我是代码不加冰今天给大家继续带来每日的刷题笔记。摘要本文探讨了计算完全二叉树节点数量的高效算法。传统遍历方法时间复杂度为O(n)而本文提出的优化算法利用完全二叉树特性通过比较左右子树高度来判断是否为满二叉树从而直接计算部分节点数。当左右高度相等时左子树为满二叉树否则右子树为满二叉树。满二叉树的节点数可用公式2^height-1计算。该算法通过递归处理非满子树将时间复杂度降至O(log²n)。文中详细解析了算法执行过程并通过示例演示了如何逐步计算节点总数最终实现比常规遍历更高效的解决方案。题目背景给你一棵完全二叉树的根节点root求出该树的节点个数。完全二叉树 的定义如下在完全二叉树中除了最底层节点可能没填满外其余每层节点数都达到最大值并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第h层从第 0 层开始则该层包含1~ 2h个节点。示例 1输入root [1,2,3,4,5,6]输出6示例 2输入root []输出0示例 3输入root [1]输出1提示树中节点的数目范围是[0, 5 * 104]0 Node.val 5 * 104题目数据保证输入的树是完全二叉树进阶遍历树来统计节点是一种时间复杂度为O(n)的简单解决方案。你可以设计一个更快的算法吗题目解析基础知识首先我们要知道什么是完全二叉树关键区别并不是每个节点都有左右子节点而是每一层能达到的最大节点数。完全二叉树假设树的高度为 h根节点在第1层那么第1层到第 h-1 层每一层的节点数都达到最大值即 2^(层数-1) 个节点第 h 层最后一层节点都连续靠左排列可以不满可以看出如果整个树不是满二叉树就递归其左右孩子直到遇到满二叉树为止用公式计算这个子树满二叉树的节点数量。这里关键在于如何去判断一个左子树或者右子树是不是满二叉树呢在完全二叉树中如果递归向左遍历的深度等于递归向右遍历的深度那说明就是满二叉树。如图用数组存储来理解完全二叉树可以用数组连续存储这是堆排序的基础。java// 完全二叉树 [1,2,3,4,5,6] // 数组索引0 1 2 3 4 5 // 节点值 1 2 3 4 5 6 // 索引关系 // 节点 i 的左子节点 2*i 1 // 节点 i 的右子节点 2*i 2关键数组中没有空洞没有 null 值所有节点连续排列。text完全二叉树 1 / \ 2 3 / \ / 4 5 6 数组[1, 2, 3, 4, 5, 6] ← 连续没有空洞 ✅ 非完全二叉树 1 / \ 2 3 / \ 4 5 数组[1, 2, 3, 4, null, null, 5] ← 有空洞 ❌首先我们要知道数组存储的顺序是层序遍历这样就能解释为什么最后一层靠左的时候二叉树还是完全二叉树靠右是不行的例子如下靠右排列不是完全二叉树text1 / \ 2 3 / \ \ 4 5 6 问题节点3没有左子节点但有右子节点6 层序遍历应该怎么排 按层序遍历规则 第1层1 第2层2, 3 第3层先遍历2的左子节点42的右子节点5然后3的左子节点(null)3的右子节点6 结果[1, 2, 3, 4, 5, null, 6]关键层序遍历序列中出现了null不连续解法1最简单的解法就是普通的二叉树的遍历方法遍历整棵树统计节点因为题目要返回的就是二叉树的节点。这种解法有两种方式就是递归法和层序遍历解法BFS两种方式的时间复杂度都是On这两种方式我们在前面已经很了解了有不清楚的可以去我的LeetCode刷题日记专栏中看二叉树相关的文章这是普遍的方法但我们这里处理的是一种特殊的二叉树肯定有特殊的办法来处理。解法2正如题目所说的进阶方法有一种更快的解法完全二叉树有一个重要性质如果左子树的高度等于右子树的高度则左子树是满二叉树如果左子树的高度大于右子树的高度则右子树是满二叉树。满二叉树的节点数可以直接用公式计算2^height - 1利用这个性质我们不需要遍历所有节点只需要沿着树的左右边界计算高度然后递归处理不满的那棵子树。左子树高度 2路径节点2 → 节点4节点5没有被计入在计算节点数时满二叉树的公式2^高度 - 1计算的是整棵满二叉树的所有节点包含节点5text2 / \ 4 5 这是一棵高度为2的满二叉树 - 节点2, 4, 5 - 节点数 2^2 - 1 3 ✅包含了5答案根节点(1) 左子树中满二叉树的部分(2,4,5)text(1 leftHeight) 4 拆解 ┌─────────────────────────────────────────┐ │ 这个4包含的节点 │ │ │ │ 1 ← 根节点1个 │ │ / │ │ 2 ← 左子树的根1个 │ │ / \ │ │ 4 5 ← 左子树的子节点2个 │ │ │ │ 小计1 1 2 4 ✅ │ └─────────────────────────────────────────┘为什么是2^leftHeight而不是2^leftHeight - 1因为2^leftHeight - 1是左子树本身的节点数不包含根节点1。表达式计算包含的节点2^leftHeight - 14-13左子树2,4,52^leftHeight4根节点1 左子树1,2,4,5所以(1 leftHeight)巧妙地一次性包含了根节点 满的左子树当leftHeight rightHeight时说明左子树比右子树深右子树一定是一个满二叉树因为完全二叉树的节点都是靠左的右子树不满的话左边也不能满右子树的高度 rightHeight执行过程第一层调用countNodes(1)1. 计算左高度永远只往左走从1.left 22.left 44.left null走了2 步左高度 22. 计算右高度永远只往左走从1.right 33.left null走了1 步右高度 13. 比较不是 相等走else分支javareturn (1 右高度) countNodes(左子树) (1 1) countNodes(2) 2 countNodes(2)这 2 是什么1 1 2它就是根节点 1 右子节点 3✅ 到这里已经确定1和3直接算完了不需要进去看 3 下面。三、进入countNodes(2)递归当前树是text2 / \ 4 51. 计算左高度从2.left 44.left null走了1 步左高度 12. 计算右高度从2.right 55.left null走了1 步右高度 13. 比较相等走相等分支javareturn (1 左高度) countNodes(右子树) (1 1) countNodes(5) 2 countNodes(5)这 2 是什么1 1 2它就是根节点 2 左子节点 4✅ 到这里已经确定2和4直接算完不需要进去看 4 下面。四、进入countNodes(5)递归当前树text51. 左高度5.left null → 02. 右高度5.right null → 03. 相等javareturn (1 0) countNodes(null) 1 0 1五、从下往上汇总textcountNodes(5) 1 countNodes(2) 2 1 3 countNodes(1) 2 3 5最终结果5 ✅设计巧妙普通递归O(n) count(node) 1 count(left) count(right) 需要遍历所有节点 优化算法O(log²n) 利用完全二叉树特性直接计算满二叉树部分 关键洞察 2^height 1(根节点) (2^height - 1)(满子树) ↑ ↑ 多出来的1 满子树本身的节点数题目答案class Solution { // 通用递归解法 public int countNodes(TreeNode root) { if(root null) { return 0; } return countNodes(root.left) countNodes(root.right) 1; } }class Solution { // 迭代法 public int countNodes(TreeNode root) { if (root null) return 0; QueueTreeNode queue new LinkedList(); queue.offer(root); int result 0; while (!queue.isEmpty()) { int size queue.size(); while (size -- 0) { TreeNode cur queue.poll(); result; if (cur.left ! null) queue.offer(cur.left); if (cur.right ! null) queue.offer(cur.right); } } return result; } }class Solution { /** * 针对完全二叉树的解法 * * 满二叉树的结点数为2^depth - 1 */ public int countNodes(TreeNode root) { if (root null) return 0; TreeNode left root.left; TreeNode right root.right; int leftDepth 0, rightDepth 0; // 这里初始为0是有目的的为了下面求指数方便 while (left ! null) { // 求左子树深度 left left.left; leftDepth; } while (right ! null) { // 求右子树深度 right right.right; rightDepth; } if (leftDepth rightDepth) { return (2 leftDepth) - 1; // 注意(21) 相当于2^2所以leftDepth初始为0 } return countNodes(root.left) countNodes(root.right) 1; } }结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励