无递归树遍历的空间复杂度

该代码遍历树，但不使用递归，用堆栈替换它。堆栈的最大大小应该是最后一级中的节点数。是以下代码的空间复杂度：O（高度），其中root的高度是0？无递归树遍历的空间复杂度

public void preOrder() { 
    if (root == null) throw new IllegalStateException("the root cannot be null"); 

    final Stack<TreeNode<E>> stack = new Stack<TreeNode<E>>(); 
    stack.add(root); 

    while (!stack.isEmpty()) { 
     final TreeNode<E> treeNode = stack.pop(); 
     System.out.print(treeNode.item + " "); 
     if (treeNode.right != null) stack.add(treeNode.right); 
     if (treeNode.left != null) stack.add(treeNode.left); 
    } 
}

来源

2014-12-25 JavaDeveloper

是的，你是正确的，但不是O（2^height）与O（N）相同，其中N是树中最坏情况下的节点数。在最坏的情况下，堆栈的最大尺寸也可以是N. – sashas

代码中唯一的空间用法来自您的Stack<>中的元素。正如你在问题中所观察到的那样，在任何点Stack<>的大小都是当前节点的深度（即距离根的距离），因此算法的空间复杂度为O(height)。例如，如果您有一个平衡的二叉树，O(height)可能低至O(log V)，其中V是树中顶点的数量。在最坏的情况下，O(height) = O(V)。

来源

2014-12-25 23:42:10 Pradhan

无递归树遍历的空间复杂度

回答

相关问题