求非空二叉树的宽度

二叉树是一类常见的数据结构，其中每个节点最多有两个子节点，这里我们讨论的是非空二叉树的宽度问题。在算法设计与分析中，宽度常常作为非空二叉树复杂度的重要指标之一。宽度泛指每层的节点数与各层节点数的最大值中的较大者，下面从不同角度来分析如何求解非空二叉树的宽度问题。

1. 递归法

首先，我们可以采用递归法求解非空二叉树的宽度。对于每个节点，我们可以很容易地计算出它的左右子树的宽度，并将其加起来即可得到该节点所在子树的宽度。递归终止的条件是当节点为叶子节点时，返回节点数为1。这种方法的时间复杂度为O(n^2)，因为需要对每个节点都进行一次遍历。

2. 层次遍历法

另一种求解非空二叉树宽度的方法是层次遍历法。该方法是指按层次顺序依次遍历每个节点，并记录每层的节点数，最后求出所有层节点数的最大值。这种方法的时间复杂度为O(n)，是一种高效的解法。

3. 动态规划法

动态规划是一种常见的算法设计方法，也可以用来求解非空二叉树宽度问题。我们可以用一个动态数组记录每层节点数，并计算出每个节点的左右子树宽度之和。这种方法的时间复杂度同样为O(n)，与层次遍历方法相当。

4. DFS法

递归和动态规划属于深度优先搜索（DFS）算法的实现，而层次遍历法则是广度优先搜索（BFS）算法的实现。因此，我们还可以使用DFS算法来求解非空二叉树宽度。具体来说，我们可以遍历每个节点并记录其所在层数，再计算出每层的节点数，最后求出最大值。时间复杂度为O(n)。