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

Question

这段代码遍历树，但没有使用递归，而是用栈代替。栈的最大大小，应该是最后一层的节点数。下面代码的空间复杂度是O(height)，其中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); 
    }
}

Answer 1

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