二叉树结点数算法

二叉树是一种非常常用的数据结构，它由结点以及连接这些结点的边组成。在任意一个结点上，它可以有0~2个子结点，所以我们称之为二叉树。在实际应用中，对二叉树结点数的算法问题也经常得到提及。在这篇文章中，我们将从多个角度去分析二叉树结点数算法。

1.二叉树结点数算法的递归实现

在二叉树中，每个结点都可以看做是根结点，因此我们可以对每个结点再递归求解其左子树和右子树的结点数。具体实现如下所示:

```

int countNodes(TreeNode* root) {

if (!root) return 0;

return 1 + countNodes(root->left) + countNodes(root->right);

}

```

在该递归实现中，我们从底向上递归，最终得到了整棵二叉树的结点数。由于每个结点都会被遍历一次，所以时间复杂度为O(n)，其中n为二叉树中结点的个数。

2.二叉树结点数的迭代实现

除了递归实现之外，我们还可以使用迭代的方式去计算二叉树的结点数。具体思路是使用队列(queue)来存储每一层的结点，并遍历队列中的每个结点，统计结点个数。

```

int countNodes(TreeNode* root) {

if (!root) return 0;

int ans = 0;

queue q{{root}};

while (!q.empty()) {

auto t = q.front(); q.pop();

ans++;

if (t->left) q.push(t->left);

if (t->right) q.push(t->right);

}

return ans;

}

```

在该迭代实现中，我们在外层使用while循环来遍历队列中的每个结点，并在内层对每个结点的左子结点和右子结点进行入队操作，同时统计结点个数。由于每个结点只会被遍历一次，所以时间复杂度为O(n)，其中n为二叉树中结点的个数。

3.叶子节点计数法

在很多场景下，我们只关心二叉树的叶子结点的数量，而不需要考虑内部的结点。在这种情况下，我们可以使用叶子节点的计数方式去求解。

具体实现是使用递归的方式：对于每个结点，我们返回其左子结点的叶子节点数与右子结点的叶子节点数之和。对于叶子结点本身，返回1。具体代码如下：

```

int countNodes(TreeNode* root) {

if (!root) return 0;

if (!root->left && !root->right) return 1;

return countNodes(root->left) + countNodes(root->right);

}

```

由于每个叶子结点只会被遍历一次，所以时间复杂度为O(n)，其中n为二叉树中结点的个数。

通过以上分析，我们可以看出二叉树结点数算法有多种实现方式，我们可以根据具体的场景去选择最优的实现方式。