算法相对较新，所以请原谅我遗漏了一些明显的东西！
我知道深度优先搜索的空间复杂度通常表示为O（H），其中H是树的高度，而广度优先搜索的复杂性是O（n），其中n是树中节点的数目。
我理解这样的解释（比如在这个答案中https://stackoverflow.com/a/9844323/10083571），在最坏的情况下，在bfs中，所有节点都在一个级别上，这意味着我们必须在遍历所有节点之前将它们排队。我也知道树的空间复杂度将由它的高度决定，因为这将决定堆栈上的最大层，这些层需要被存储起来。
我不明白的是，为什么这个也不表示为o（n）。与bfs的最坏情况类似，dfs的最坏情况不是所有节点都位于彼此之下，沿着一个血统吗？所以在最坏的情况下，树的高度将等于它拥有的节点数那么为什么这个也不表示为o（n）？
感谢
最佳答案
是的，但那不是一棵树，而是一个链表big-o是抽象的；当它声称对树的搜索是lg（n）时，它意味着一个适当平衡的树，而不是一个病理构造的树。