二叉树广度优先搜索的空间复杂度？

Question

二叉树上广度优先搜索的空间复杂度是多少？因为它一次只存储一个级别，我不认为它会是O（n）。

Answer 1

空间复杂度实际上是O（n），正如一个完美的二叉树所见证的那样。考虑深度四的示例：

                  ____________________14____________________
                 /                                          \
         _______24_________                        __________8_________
        /                  \                      /                    \
     __27__             ____11___             ___23___              ____22___
    /      \           /         \           /        \            /         \
  _4        5        _13         _2        _17        _12        _26         _25
 /  \      / \      /   \       /  \      /   \      /   \      /   \       /   \
29   0    9   6    16    19    20   1    10    7    21    15   18    30    28    3

请注意，每个深度的节点数由下式给出

depth num_nodes
0     1
1     2
2     4
3     8
4     16

通常，在深度d处有2^d节点。深度为d的完美二叉树中的节点总数为n=1 2^1 2^2…2^d=2^（d1）-1。当＜code＞d

插图的功劳归于binarytree包。