这是层序遍历的代码:
public void bfsTraveral() {
if (root == null) {
throw new NullPointerException("The root cannot be null.");
}
int currentLevelNodes = 0;
int nextLevelNodes = 0;
final Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
currentLevelNodes++;
while(!queue.isEmpty()) {
final TreeNode node = queue.poll();
System.out.print(node.element + ",");
currentLevelNodes--;
if (node.left != null) { queue.add(node.left); nextLevelNodes++;}
if (node.right != null) { queue.add(node.right); nextLevelNodes++;}
if (currentLevelNodes == 0) {
currentLevelNodes = nextLevelNodes;
nextLevelNodes = 0;
System.out.println();
}
}
在我看来,空间复杂度应该是 O(2^h),其中 h 是树的高度,仅仅是因为这是队列在执行期间可达到的最大大小。在互联网上,我发现空间复杂度为 O (n)。这对我来说听起来不正确。请分享您的意见。
谢谢,
最佳答案
如果您考虑一下,在一个有 n 个节点的树中,您不可能在任何时候将超过 n 个节点放入队列,因为没有节点会被两次入队。这给出了 O(n) 的直接上限。不过,这并不是一个严格的界限,因为如果树是一个退化链表,那么内存使用量将仅为 O(1)。
您的 O(2h) 上限也是正确的,但它的上限较弱。在一棵高度为 h 的树中,底层最多 2h 个节点,但并不能保证确实如此。如果树是一个退化链表,高度是 O(n),而你的 O(2h) 的边界将以指数方式过度逼近内存使用量。
因此,您的界限是正确的,但 O(n) 是一个更好的界限。
希望这对您有所帮助!
关于java - level order traversal遍历使用队列的空间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17635950/