统计二叉树的结点总数

二叉树是一种经典的数据结构，在计算机科学中有着广泛的应用。对于二叉树而言，其最基本的操作之一就是统计其结点总数。在本文中，我们将从多个角度来探讨如何统计二叉树的结点总数。

角度一：递归法

递归法是一种基本的解决二叉树问题的方法。对于一棵二叉树来说，其结点总数等于其根节点的结点数加上其左子树和右子树中结点的总数。因此，可以通过递归的方式来求出一棵二叉树的结点总数。具体实现如下：

```python

def countNodes(root) -> int:

if not root:

return 0

return 1 + countNodes(root.left) + countNodes(root.right)

```

该算法的时间复杂度为O(n)，其中n为二叉树的结点数。

角度二：迭代法

除了递归法之外，我们还可以使用迭代法来统计二叉树的结点总数。具体实现如下：

```python

def countNodes(root) -> int:

count = 0

stack = [root]

while stack:

node = stack.pop()

if node:

count += 1

stack.append(node.left)

stack.append(node.right)

return count

```

该算法的时间复杂度为O(n)，其中n为二叉树的结点数。

角度三：完全二叉树特性法

对于满足完全二叉树特性的二叉树，可以使用其特定的性质来计算其结点总数，具体实现如下：

```python

def countNodes(root) -> int:

if not root:

return 0

level = 0

node = root

while node.left:

level += 1

node = node.left

l, r = 2 ** level, 2 ** (level + 1) - 1

while l < r:

mid = (l + r + 1) >> 1

if exists(root, level, mid):

l = mid

else:

r = mid - 1

return l

def exists(root, level, k):

bits = 1 << (level - 1)

node = root

while node and bits > 0:

if not (bits & k):

node = node.left

else:

node = node.right

bits >>= 1

return node is not None

```

该算法的时间复杂度为O(log^2 n)，其中n为二叉树的结点数。