BFS和DFS在二叉树上的运行时是O(N)吗？
我意识到BFS和DFS在一般图上的运行时间是O(n+m)，其中n是节点数，m是边数，这是因为对于每个节点，必须考虑它的邻接列表。但是，当BFS和DFS在二叉树上执行时，它的运行时是什么呢？我相信它应该是O(n)，因为可以走出一个节点的边的可能数量是恒定的（即2）。请确认这是否是正确的理解。如果不是，那么请解释一个二叉树上BFS和DFS的正确时间复杂度是多少？
共有1个答案
BFS和DFS的时间复杂性只是O(E)，或者在您的情况下，O(m)。
在二叉树中，m等于n-1，因此时间复杂度等于O(V)。m是指边的总数，而不是每个顶点相邻边的平均数。
-
给定一个二叉树，我想返回最大和子树的根。 最大子树：树的子树，其所有节点的总和大于任何其他子树的总和。 编辑：节点值为整数。 我可以做以下需要O（n^2）的事情。 计算左子树中所有节点的总和 计算右子树中所有节点的总和 如果左子树和右子树的和以及根的值大于当前最大和，则根存储在结果中 以左子树作为根递归调用此函数 以右子树作为根递归调用此函数。这将需要O（n^2） 我可以将其更改为自底向上的方法，
-
问题内容： 这不是功课，这是一个面试问题。 这里的要点是算法应该是恒定空间。我对没有堆栈的情况一无所知，我会发布我使用堆栈编写的内容，但是无论如何都没有关系。 这是我尝试的方法：我尝试进行预遍历，但到达了最左边的节点，但是我被卡在那里。我不知道如何在没有堆栈/父指针的情况下“递归”备份。 任何帮助，将不胜感激。 （我将其标记为Java，因为这是我很喜欢使用的语言，但是显然它与语言无关。） 问题答案
-
我有一个无向图，从中我重新绘制了相同的图，但是是树状结构(有层次)。我知道广度优先搜索(BFS)算法是如何工作的，但我不知道如何从图转换 在这里，在维基百科的这篇文章中，如果你向下滚动一点，你会看到两张德国城市的照片。即使在阅读了那里的伪代码后，我还是不明白你是如何从第一张照片变成第二张的。
-
QSTN：当它是叶节点时，为什么需要初始化ls=0或rs=0。考虑链接中给出的树，如果我们到达节点4，如果(node==NULL isLeaf（node））返回1；上面的代码将1（true）返回到调用它的函数，即节点10，类似地，右侧将true返回到节点10，因此我们现在可以进入下面的循环，因为如果(isSumTree(node->left)&&isSumTree(node->left)&&isS
-
我试图打印二叉树的所有路径（根到叶的路径），但没有效果。 我的策略是使用递归，基本情况是树为None或树节点为leaf return，否则，遍历树的左侧和右侧。 但我找不到同时保留左右树的方法。
-
这是BST Add中二进制搜索树中add的实现 我的问题是，即使二元搜索树是不平衡的，同样的策略是否也能用于分析add的运行时？你要做多少次切割。运行时不是仍然是O（logn），而不是O（n）吗？如果是这样的话，有人能证明为什么它会是O（n）吗？