222.完全二叉树的节点个数

bfs, dfs, binary + greedy, https://leetcode.cn/problems/count-complete-tree-nodes/

如果用bfs, dfs写是简单级别，binary search是中级难度。

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

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

示例 1：

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

示例 2：

输入：root = []
输出：0

示例 3：

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

提示：

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

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

思路：直接递归很简单

优化的话利用完全二叉树的性质，左右子树至少有一个是满二叉树，可以直接得出节点数目。学习了一下二进制运算符（满二叉树的节点数为 2^h - 1，其中 h 是树的高度。使用左移运算符可以高效地计算 2^h）

# 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 not root:
            return 0
        leftnum = self.countNodes(root.left)
        rightnum = self.countNodes(root.right)
        return 1+leftnum +rightnum
#以下是利用完全二叉树性质的解法
class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        left_height = self.get_height(root.left)
        right_height = self.get_height(root.right)
        
        if left_height == right_height:
            # 左子树是满二叉树
            return (1 << left_height) + self.countNodes(root.right)
        else:
            # 右子树是满二叉树
            return (1 << right_height) + self.countNodes(root.left)
    
    def get_height(self, node):
        height = 0
        while node:
            height += 1
            node = node.left
        return height

核心逻辑

在完全二叉树中：

如果 left_height == right_height，则说明左子树是满二叉树。 如果 left_height != right_height，则说明右子树是满二叉树。 这是因为：

完全二叉树的节点从左到右依次填满，所以如果左右子树的高度相等，左子树必然是满二叉树。 如果左右子树的高度不相等，则右子树必然是满二叉树（因为右子树的高度比左子树少一层）。

bfs

from collections import deque

# 定义树节点类
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: TreeNode) -> int:
        # 如果根节点为空，直接返回 0
        if not root:
            return 0
        
        # 初始化队列和计数器
        queue = deque([root])
        count = 0
        
        # 使用 BFS 遍历树
        while queue:
            node = queue.popleft()
            count += 1  # 每访问一个节点，计数器加 1
            
            # 将左右子节点加入队列（如果存在）
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        return count

思路：起初用简单的dfs思路AC了，但时间复杂度不够好看，于是尝试新方法，看了题解中的二进制思路后大受震撼，故用二进制思路走了一遍。

from typing import Optional

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 not root:
            return 0

        def check(node_index: int, current_node: Optional[TreeNode]) -> bool:
            """
            检查编号为 node_index 的节点是否存在。
            :param node_index: 节点编号（从 1 开始）
            :param current_node: 当前遍历到的节点
            :return: 如果节点存在返回 True，否则返回 False
            """
            # 将节点编号转换为二进制路径（去掉 '0b' 前缀）
            path = bin(node_index)[3:]
            for direction in path:
                if direction == '0':
                    current_node = current_node.left
                else:
                    current_node = current_node.right
                # 如果当前节点为空，说明该路径不存在
                if not current_node:
                    return False
            return True

        # 计算树的高度（从根节点到最深左子节点的路径长度）
        height = 0
        current = root
        while current.left:
            height += 1
            current = current.left

        # 二分查找最后一层的节点范围
        left, right = 2 ** height, 2 ** (height + 1) - 1
        while left < right:
            mid = (left + right) // 2
            if check(mid, root):
                left = mid + 1  # 编号 mid 存在，尝试更大的编号
            else:
                right = mid  # 编号 mid 不存在，尝试更小的编号

        # 检查最终结果是否包含最后一个节点
        return left if check(left, root) else left - 1

这题是关于“完全二叉树的节点个数”，如果使用普通遍历，时间复杂度是 O(n)。但由于题目保证这是一棵“完全二叉树”，可以利用它的结构性质设计一个更快的算法 —— $O(log²n)$。

---

✅ 思路：利用完全二叉树的高度特性（二分 + 递归）

💡 完全二叉树的特性：

• 除了最后一层，其他每一层的节点数都达到最大；
• 最后一层节点从左到右连续排列；
• 所以我们可以利用“左子树和右子树高度是否相等”来判断哪边是满的。

---

✅ 算法步骤

1. 对于当前节点：
   - 计算左子树的深度 left_depth（从左一路到底）
   - 计算右子树的深度 right_depth（从右一路到底）

2. 如果 left_depth == right_depth：
   → 说明是满二叉树，节点个数是 2^depth - 1；
3. 否则：
   → 左右子树继续递归统计。

---

✅ 代码（Python）

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        def get_depth(node, go_left=True):
            depth = 0
            while node:
                depth += 1
                node = node.left if go_left else node.right
            return depth

        left_depth = get_depth(root, True)
        right_depth = get_depth(root, False)

        if left_depth == right_depth:
            # 是满二叉树
            return (1 << left_depth) - 1
        else:
            return 1 + self.countNodes(root.left) + self.countNodes(root.right)

---

✅ 时间复杂度分析

• get_depth() 的时间是 O(log n)
• 每层递归最多进行一次 get_depth()，最多递归 log n 层
• 所以总复杂度为 $O((logn)²)$，比 O(n) 快很多

利用完全二叉树的特性，结合 二分查找（Binary Search）+ 贪心（Greedy） 来将时间复杂度从 O(n) 降低到 O(log² n)。

---

✅ 思路总结：

1. 完全二叉树的性质：

   • 如果左子树和右子树的高度一样，说明左子树是满的，可以跳过左子树直接查右子树；
   • 如果右子树高度比左子树小，则右子树是满的，可以跳过右子树查左子树；
   • 利用这个可以实现递归或二分。

2. 使用二分查找判断最后一层节点是否存在：

   • 先计算整棵树的高度 h（即从根节点走到最左下角的深度）；
   • 在 [0, 2^h - 1] 范围内用二分查找判断某个索引是否存在；
   • 最后总节点数 = 2^h - 1（前 h 层的满节点）+ left（最后一层的节点个数）。

---

🔍 Python 实现（Binary Search + Greedy）：

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: TreeNode) -> int:
        if not root:
            return 0

        def getDepth(node):
            # 计算从当前节点到最左边叶子的深度
            d = 0
            while node.left:
                node = node.left
                d += 1
            return d

        def exists(idx, depth, node):
            # 判断idx编号的节点是否存在于最后一层
            left, right = 0, 2 ** depth - 1
            for _ in range(depth):
                mid = (left + right) // 2
                if idx <= mid:
                    node = node.left
                    right = mid
                else:
                    node = node.right
                    left = mid + 1
                if not node:
                    return False
            return True

        depth = getDepth(root)
        if depth == 0:
            return 1  # 只有一个节点

        # 二分查找最后一层的节点数
        left, right = 0, 2 ** depth - 1
        while left <= right:
            mid = (left + right) // 2
            if exists(mid, depth, root):
                left = mid + 1
            else:
                right = mid - 1

        # 总节点数 = 前面满的节点 + 最后一层的实际节点数
        return (2 ** depth - 1) + left

---

✅ 时间复杂度分析：

• getDepth：O(log n)
• 每次 exists 判断走 depth 层，O(log n)
• 二分查找次数为 log(n)
• 所以总复杂度是 O((log n)²)。

这个问题的解法里，确实用了 两层二分，我们来分开讲清楚它们的目的和操作方式。

---

🔍 二分查找一：在最后一层找有多少节点

🧠 背景：

完全二叉树中，前 h 层一定是满的（即节点数是 2^h - 1），最后一层最多有 2^h 个节点，编号为 [0, 2^h - 1]。

我们要找的是：最后一层到底有多少个节点存在？

---

🧪 怎么找？

我们对最后一层的编号区间 [0, 2^h - 1] 做 二分查找，判断编号为 mid 的节点是否存在。

如果 mid 存在，说明左边都是满的，可能还有更多 → 查右边；

如果 mid 不存在，说明超出了当前树 → 查左边。

这就是外层二分：

left, right = 0, 2 ** depth - 1
while left <= right:
    mid = (left + right) // 2
    if exists(mid, depth, root):  # 二分查找是否存在这个编号
        left = mid + 1
    else:
        right = mid - 1

最终，left 就是最后一层真实存在的节点数。

---

🔍 二分查找二：exists() 函数内部，用编号查路径

🧠 背景：

现在我们要判断某个编号 idx（从 0 开始）对应的节点是否存在于完全二叉树的最后一层。

但我们没有树的数组表示，要从根节点走路径到目标位置。问题是我们只知道编号 idx，不知道怎么走。

---

🧪 怎么用二分走路径？

我们假设最后一层的编号范围是 [0, 2^depth - 1]，每次根据 idx 和中间值 mid 来判断：

• 如果 idx <= mid，目标在左子树，往左走；
• 否则在右子树，往右走；

这样从根开始走 depth 步，模拟走到 idx 这个位置，看看这个路径上有没有空节点。

def exists(idx, depth, node):
    left, right = 0, 2 ** depth - 1
    for _ in range(depth):
        mid = (left + right) // 2
        if idx <= mid:
            node = node.left
            right = mid
        else:
            node = node.right
            left = mid + 1
        if not node:
            return False
    return True

---

✅ 小结：

目的	二分查找的位置	查找什么	操作
外层二分	[0, 2^depth - 1]	最后一层有多少节点	countNodes 主体中
内层二分	路径 [0, 2^depth - 1]	某个编号的节点是否存在	exists() 中