Why is binary search useful for counting nodes in a complete tree?

Binary search allows checking positions in the last level without traversing every node, leveraging the complete tree structure for efficiency.

Can this approach handle empty trees?

Yes, the algorithm correctly returns zero when the root is null, avoiding errors in height calculations.

Is recursion necessary for Count Complete Tree Nodes?

Recursion simplifies height-based calculations, but iterative methods with bit manipulation can achieve the same sublinear performance.

What is the time complexity of this solution?

The optimized approach runs in O((log n)^2) time due to recursive height checks combined with binary search on the last level.

How does bit manipulation improve last-level node checks?

Bit shifts represent paths from root to nodes, allowing fast left/right navigation to verify node existence without full traversal.

#222

Easy

auto_awesome二分·树·traversal

LeetCode 题解工作台

完全二叉树的节点个数

给你一棵完全二叉树的根节点 root ，求出该树的节点个数。完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（从第 0 层开始），则该层包含 1~ 2 h 个节点。示例 1：…

二分查找位运算树二叉树

题目描述

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（从第 0 层开始），则该层包含 1~ 2^h 个节点。

示例 1：

输入：root = [1,2,3,4,5,6]
输出：6

示例 2：

输入：root = []
输出：0

示例 3：

输入：root = [1]
输出：1

提示：

树中节点的数目范围是[0, 5 * 10⁴]
0 <= Node.val <= 5 * 10⁴
题目数据保证输入的树是 完全二叉树

进阶：遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？

lightbulb

解题思路

方法一：递归

递归遍历整棵树，统计结点个数。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为树的结点个数。

1

2

3

4

5

6

7

8

9

10

11

12

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        return 1 + self.countNodes(root.left) + self.countNodes(root.right)

speed

复杂度分析

指标	值
时间	complexity can reach O((log n)^2) due to height computations and binary searches on the last level. Space complexity is O(log n) from recursion stack, or O(1) if iterative traversal is used.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ask candidates to explain why naive traversal is not optimal for complete trees.
question_mark
Probe if they can calculate subtree node counts using height differences.
question_mark
Listen for recognition of binary search application on the last level of a complete tree.

warning

常见陷阱

外企场景

error
Failing to exploit tree completeness and scanning all nodes unnecessarily.
error
Miscomputing tree height or assuming all levels are completely filled.
error
Incorrectly handling empty trees or last-level node counts.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count nodes in a perfect binary tree, simplifying the height comparison step.
arrow_right_alt
Determine the number of leaf nodes only, focusing traversal on the last level.
arrow_right_alt
Apply the approach to a k-ary complete tree with similar height-based optimizations.

help

常见问题

外企场景

继续练习

#226 翻转二叉树 #230 二叉搜索树中第 K 小的元素 #235 二叉搜索树的最近公共祖先