二叉树层次遍历的空间复杂度

二叉树的层次遍历是一种广度优先搜索的算法，它按照从上到下、从左到右的顺序遍历二叉树的每个节点。在层次遍历过程中，我们需要使用一个队列来存储待遍历的节点。因此，空间复杂度取决于队列中存储的节点数量。

假设二叉树的节点数为n，最坏情况下，当二叉树为满二叉树时，最后一层的节点数为n/2个。在层次遍历过程中，队列中最多会存储n/2个节点。因此，二叉树层次遍历的空间复杂度为O(n)。

相关问题

用递归实现二叉树的层次遍历

递归实现二叉树的层次遍历相对不太常见，但是可以通过递归实现。递归实现二叉树的层次遍历需要借助队列，具体步骤如下：

1. 定义一个队列，将根节点入队；
2. 定义一个辅助函数，该函数接收一个队列作为参数，并将队列中的节点按照层次顺序出队并访问其值，同时将其左右子节点入队；
3. 调用辅助函数，开始遍历。

下面是实现代码：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def levelOrder(root):
    res = []
    if not root:
        return res

    def dfs(node, depth):
        if len(res) == depth:
            res.append([])
        res[depth].append(node.val)
        if node.left:
            dfs(node.left, depth+1)
        if node.right:
            dfs(node.right, depth+1)

    dfs(root, 0)
    return res

在辅助函数 `dfs` 中，我们传入了节点和节点所处的深度，如果当前深度在结果列表中不存在，就在结果列表中添加一个新的空列表，然后将当前节点的值加入到该列表中。接着，我们判断当前节点是否有左右子节点，如果有，就调用 `dfs` 函数遍历其子节点，并将深度加 1。最后，我们调用 `dfs` 函数遍历根节点，并将深度初始化为 0，返回结果列表 `res` 即可。

需要注意的是，这种方法虽然可以实现二叉树的层次遍历，但是由于递归的过程中需要将每一层的节点都存入结果列表中，因此空间复杂度较高。如果二叉树深度较大，可能会导致栈溢出或者内存不足问题。因此，建议在实际应用中使用迭代的方式实现二叉树的层次遍历。

C语言用递归实现二叉树的层次遍历

C语言用递归实现二叉树的层次遍历相对不太常见，但是也是可以通过递归实现的。递归实现二叉树的层次遍历需要借助队列，具体步骤如下：

1. 定义一个队列，将根节点入队；
2. 定义一个辅助函数，该函数接收一个队列作为参数，并将队列中的节点按照层次顺序出队并访问其值，同时将其左右子节点入队；
3. 调用辅助函数，开始遍历。

下面是实现代码：

#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

void dfs(struct TreeNode* node, int depth, int **res, int *returnSize) {
    if (*returnSize == depth) {
        *res = (int *)realloc(*res, (*returnSize+1)*sizeof(int *));
        (*res)[*returnSize] = node->val;
        (*returnSize)++;
    } else {
        (*res)[depth] = node->val;
    }
    if (node->left) {
        dfs(node->left, depth+1, res, returnSize);
    }
    if (node->right) {
        dfs(node->right, depth+1, res, returnSize);
    }
}

int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {
    int **res = (int **)malloc(sizeof(int *));
    *returnSize = 0;
    if (!root) {
        *returnColumnSizes = NULL;
        return NULL;
    }
    dfs(root, 0, &res, returnSize);
    *returnColumnSizes = (int *)malloc(*returnSize*sizeof(int));
    for (int i = 0; i < *returnSize; i++) {
        (*returnColumnSizes)[i] = 1;
    }
    return res;
}

在辅助函数 `dfs` 中，我们传入了节点、节点所处的深度、结果列表、结果列表的大小作为参数。如果当前深度在结果列表中不存在，就在结果列表中添加一个新的空间，然后将当前节点的值加入到该列表中。接着，我们判断当前节点是否有左右子节点，如果有，就调用 `dfs` 函数遍历其子节点，并将深度加 1。最后，我们在主函数中调用 `dfs` 函数遍历根节点，并将深度初始化为 0，返回结果列表 `res` 即可。

需要注意的是，这种方法虽然可以实现二叉树的层次遍历，但是由于递归的过程中需要将每一层的节点都存入结果列表中，因此空间复杂度较高。如果二叉树深度较大，可能会导致栈溢出或者内存不足问题。因此，建议在实际应用中使用迭代的方式实现二叉树的层次遍历。