該函數用於按級別打印二叉樹級別的時間和空間複雜度

Question

該算法用於逐級打印普通二叉樹。

什麼是printSpecificLevel_BT()和printBT_LBL()的時間複雜度和空間複雜度？

我認爲printSpecificLevel_BT的時間複雜度爲O(lg N)，空間複雜度爲O(lg N)。
我認爲printBT_LBL()的時間複雜度爲O((lgN)^2)，空間複雜度爲O((lgN)^2)。

這是正確的嗎？

// Print the specific level of a binary tree. 
public static void printSpecificLevel_BT (Node root, int level) { 
    if (root == null) return; 
    if (level == 0) System.out.print(String.format("%-6d", root.data)); // Base case. 
    // Do recrusion. 
    printSpecificLevel_BT(root.leftCh, level - 1); 
    printSpecificLevel_BT(root.rightCh, level - 1); 
} 

// Get the height of a binary tree. 
public static int getHeight_BT (Node root) { 
    if (root == null || (root.leftCh == null && root.rightCh == null)) return 0; // Base case. 
    return 1 + Math.max (getHeight_BT(root.leftCh), getHeight_BT(root.rightCh)); 
} 

// Print a binary tree level by level. 
public static void printBT_LBL (Node root) { 
    // Get the height of this binary tree. 
    int height = getHeight_BT(root); 
    for (int i = 0; i <= height; i ++) { 
     printSpecificLevel_BT(root, i); 
     System.out.println(); 
    } 
} 

Answer 1

printSpecificLevel_BT是O(n)，因爲它看起來在樹中的每個節點。但是，只需簡單地更改（返回時level == 0），您可以使其成爲O(min(n, 2^level))。

getHeight是O(n)，因爲它查看樹中的每個節點。 printBT_LBL調用getHeight一次，printSpecificLevel_BTheight10次，所以其複雜度爲O(n + n*height) = O(n*height)。

每一個的空間複雜度都是O(height)，因爲它一直遞歸到樹的底部。你不能說O(log n)，因爲這棵樹不一定是平衡的（除非它是平衡的）。

Answer 2

對於printSpecificLevel_BT()您有：

對於printBT_LBL()您有：