元宝 LeetCode 222. 完全二叉树的节点个数 Java实现

LeetCode 222. 完全二叉树的节点个数 — Java 题解题目给定一棵完全二叉树的根节点“root”返回节点个数。完全二叉树除最后一层外每层全满最后一层节点靠左连续排列。✅ 推荐解法递归利用完全二叉树性质O(log²n)核心思想对当前节点分别沿最左路径和最右路径算高度左高 右高 → 左子树是满二叉树节点数 “2^leftH - 1(左子树) 1(根) 右子树节点数”左高 右高 → 右子树是满二叉树高度少 1节点数 “2^rightH - 1(右子树) 1(根) 左子树节点数”每次递归都能确定一半是满的问题规模减半。Java 代码class Solution {public int countNodes(TreeNode root) {if (root null) return 0;int leftH leftHeight(root); int rightH rightHeight(root); if (leftH rightH) { // 左子树满 return (1 leftH) countNodes(root.right); } else { // 右子树满 return (1 rightH) countNodes(root.left); } } // 沿最左路径求高度 private int leftHeight(TreeNode node) { int h 0; while (node ! null) { h; node node.left; } return h; } // 沿最右路径求高度 private int rightHeight(TreeNode node) { int h 0; while (node ! null) { h; node node.right; } return h; }}复杂度时间“O(log²n)” — 递归“O(log n)” 层每层算高度“O(log n)”空间“O(log n)” — 递归栈 最优解法二分 位掩码O(log²n)O(1) 空间核心思想树高“h”最左路径前 h 层满节点 “2^h - 1”最后一层节点从左到右连续编号“0 ~ 2^h-1”编号的二进制位表示路径“0”左“1”右二分查找最右存在的编号 kJava 代码class Solution {public int countNodes(TreeNode root) {if (root null) return 0;// 计算高度 h int h 0; TreeNode node root; while (node.left ! null) { node node.left; h; } // 二分查找最后一层最右节点 int left 0, right (1 h) - 1; while (left right) { int mid left (right - left 1) / 2; // 向上取整 if (exists(root, mid, h)) { left mid; } else { right mid - 1; } } return (1 h) - 1 left 1; } // 判断编号为 k 的节点是否存在 private boolean exists(TreeNode root, int k, int h) { TreeNode node root; for (int i h - 1; i 0; i--) { if ((k i 1) 0) node node.left; else node node.right; if (node null) return false; } return true; }} 方法对比方法 时间 空间 特点递归高度判断 O(log²n) O(log n) ✅ 推荐代码清晰易讲二分位掩码 O(log²n) O(1) 最优面试加分暴力遍历 O(n) O(log n) ❌ 未利用性质 考点总结完全二叉树高度 沿最左路径的节点数满二叉树公式高 h 有“2^h - 1” 个节点位运算“k i 1” 取第 i 位“1 h” 算 2^h二分向上取整“mid left (right - left 1) / 2”防死循环最后一层连续性是二分的前提面试建议先讲思路二逻辑直观再提思路一位运算优化展示深度。