재귀가없는 트리 순회의 공간 복잡도

Question

이 코드는 트리를 탐색하지만 재귀를 사용하지 않고 스택으로 대체합니다. 스택의 최대 크기는 마지막 레벨의 노드 수 여야합니다. 다음 코드의 공간이 복잡합니까? O (높이)? 루트 높이가 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)입니다.