無遞歸樹遍歷的空間複雜度

該代碼遍歷樹，但不使用遞歸，用堆棧替換它。堆棧的最大大小應該是最後一級中的節點數。是以下代碼的空間複雜度：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

無遞歸樹遍歷的空間複雜度

回答

相關問題