【Swift 算法实战】高效计算完全二叉树的节点数

  大家好，我是 展菲，目前在上市企业从事人工智能项目研发管理工作，平时热衷于分享各种编程领域的软硬技能知识以及前沿技术，包括iOS、前端、Harmony OS、Java、Python等方向。在移动端开发、鸿蒙开发、物联网、嵌入式、云原生、开源等领域有深厚造诣。

图书作者：《ESP32-C3 物联网工程开发实战》
图书作者：《SwiftUI 入门，进阶与实战》
超级个体：COC上海社区主理人
特约讲师：大学讲师，谷歌亚马逊分享嘉宾
科技博主：极星会首批签约作者

摘要

在二叉树的相关问题中，统计 完全二叉树 的节点个数是一个经典问题。普通的 O(n) 遍历方法可以解决，但 如何更快地计算节点数？

本文将介绍 基于二分查找 + 位运算 的 O(log² n) 高效算法，并提供 Swift 代码示例与详细分析。

描述

给你一棵 完全二叉树 的根节点 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) 的简单解决方案。你可以设计一个更快的算法吗？

题解答案

最直接的思路是使用 DFS 或 BFS 遍历整棵树，统计节点总数，时间复杂度 O(n)，但对于 n=50000 级别的数据，这并不是最优解。

高效方法

由于完全二叉树的特殊性：

1. 计算树的深度 h：可通过 沿着左子树遍历到底 计算 h，时间 O(log n)。
2. 利用二分查找计算最底层节点数：
   • 完全二叉树的总节点数介于 2^h ~ 2^(h+1)-1，需要找到 最底层最后一个节点 位置。
   • 采用 二分查找 + 位运算 判断某个索引 idx 是否存在。

最终，整个算法的时间复杂度为 O(log² n)，比 O(n) 提升显著。

题解代码分析

import Foundation

// 定义树节点结构
public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil }
}

// 主函数
func countNodes(_ root: TreeNode?) -> Int {
    guard let root = root else { return 0 }

    // 计算树深度
    func getDepth(_ node: TreeNode?) -> Int {
        var depth = 0
        var current = node
        while current != nil {
            depth += 1
            current = current?.left
        }
        return depth
    }
    
    let depth = getDepth(root)
    if depth == 1 { return 1 }  // 只有一个节点的情况
    
    // 二分查找底层最后一个节点
    let maxNodes = (1 << (depth - 1)) - 1 // 计算完整的上层节点数
    var left = 0, right = maxNodes
    
    func nodeExists(_ index: Int, _ depth: Int, _ root: TreeNode?) -> Bool {
        var node = root
        var left = 0, right = maxNodes
        for _ in 0..<(depth - 1) {
            let mid = (left + right) / 2
            if index <= mid {
                node = node?.left
                right = mid
            } else {
                node = node?.right
                left = mid + 1
            }
        }
        return node != nil
    }
    
    while left < right {
        let mid = (left + right + 1) / 2
        if nodeExists(mid, depth, root) {
            left = mid
        } else {
            right = mid - 1
        }
    }
    
    return maxNodes + left + 1
}

示例测试及结果

// 构造二叉树
let root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left?.left = TreeNode(4)
root.left?.right = TreeNode(5)
root.right?.left = TreeNode(6)

// 计算节点数
print(countNodes(root))  // 输出: 6

时间复杂度

• 计算树的深度：O(log n)
• 二分查找最后一个节点：O(log n)
• 总复杂度：O(log² n)

空间复杂度

• 仅用到常数额外空间，O(1)

总结

✅ 利用完全二叉树特性，减少遍历次数
✅ 二分查找 + 位运算，降低时间复杂度至 O(log² n)
✅ 适用于大规模数据，如 n=50000