一、问题描述

给出一个完全二叉树的根节点 root，返回这棵树的节点个数。如果完全二叉树的节点数为 N，请实现时间复杂度低于 O(N) 的解决方案

完全二叉树的定义如下：

• 每个节点都有 0 个或 2 个子节点。
• 所有的叶子节点都在同一层，且每个父节点都有两个子节点。
• 如果一个节点只有左子节点而没有右子节点，则该节点的所有子节点都在它的左子树中。

二、方案一：递归法

1、思路

递归遍历整棵树，计算节点总数。对于每个节点，我们递归地计算其左子树和右子树的节点数，然后将它们加一（当前节点）。

2、代码实现

func countNodes(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return 1 + countNodes(root.Left) + countNodes(root.Right)
}

3、复杂度分析

• 时间复杂度：最坏情况下，树是完全不平衡的，例如每个节点都只有左子节点，递归会调用 N 次，时间复杂度为 O(N)。
• 空间复杂度：空间复杂度主要取决于递归栈的深度，最坏情况下，递归栈的深度为 N，因此空间复杂度也是 O(N)。

三、方案二：迭代法

1、思路

迭代法使用队列来实现层序遍历。我们从根节点开始，将节点放入队列中，然后逐个处理队列中的节点，同时将它们的子节点加入队列。

2、代码实现

func countNodes(root *TreeNode) int {
    if root == nil {
        return 0
    }
    queue := []*TreeNode{root}
    count := 0
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        count++
        if node.Left != nil {
            queue = append(queue, node.Left)
        }
        if node.Right != nil {
            queue = append(queue, node.Right)
        }
    }
    return count
}

3、复杂度分析

• 时间复杂度：每个节点都会被处理一次，因此时间复杂度为 O(N)。
• 空间复杂度：空间复杂度取决于队列中元素的最大数量，这在最坏情况下为树的最大宽度，即 O(N)。

四、方案三：利用完全二叉树的性质

1、思路

完全二叉树的性质：如果一棵树的左子树深度为 d，右子树深度为 d-1，则该树有 2^d - 1 个节点。利用这个性质，我们可以减少不必要的遍历。

2、代码实现

func countNodes(root *TreeNode) int {
    if root == nil {
        return 0
    }
    left, right := root, root
    leftDepth, rightDepth := 0, 0
    for left != nil {
        left = left.Left
        leftDepth++
    }
    for right != nil {
        right = right.Right
        rightDepth++
    }
    if leftDepth == rightDepth {
        return (1 << leftDepth) - 1
    }
    return 1 + countNodes(root.Left) + countNodes(root.Right)
}

3、复杂度分析

• 时间复杂度：最坏情况下，我们需要遍历整棵树来计算深度，时间复杂度为 O(N)。但在完全二叉树的情况下，我们通常可以在 O(logN * logN) 的时间内找到节点数。
• 空间复杂度：O(1)，因为我们没有使用额外的空间。

五、总结

方案	时间复杂度	空间复杂度
递归法	O(N)	O(N)
迭代法	O(N)	O(N)
利用完全二叉树性质	O(logN * logN)	O(1)

在大多数情况下，利用完全二叉树的性质的方法是最高效的，因为它的时间复杂度低于 O(N)，并且空间复杂度为 O(1)。