時間比較：運營商

我寫一個函數返回二叉樹的最大深度。時間比較：運營商

class Solution { 
public: 
    int maxDepth(TreeNode* root) { 
     if(root == 0) return 0; 
     if((root -> left ==0) &&(root->right == 0)) return 1; 
     ************** 
    } 
};

我寫爲*****部分方法一兩種方法：

else return max((1+maxDepth(root -> left)),(1+maxDepth(root -> right)));

方法2：

else return (maxDepth(root -> left) > maxDepth(root -> right)) ? 
      (maxDepth(root->left) + 1): 
      (maxDepth(root->right) + 1);

第二種方法失敗而第一個經過定時檢查。他們看起來很像我。任何人都可以提供一些提示，爲什麼第二種方法更慢？

來源

2017-09-15 cxf54

那麼，這些完全不相似。你在第一個例子中調用'maxDepth'兩次，在第二個例子中調用_three_ ... – Obicere

@Obicere三次。 – pvg

@pvg，對不起，這是正確的。儘管如此，它對於他在這裏看到的時差還是足夠重要的。 – Obicere

第一種方法是相似的：

else { 
    auto l = 1 + maxDepth(root -> left); 
    auto r = 1 + maxDepth(root -> left); 

    return (l > r) ? l : r; 
}

注意maxDepth()只被調用兩次。

在第二種方法中，在條件表達式中調用maxDepth()兩次，然後在true-expression或false-expression（取決於條件的結果）中第三次調用maxDepth()。這浪費時間重新計算價值。

根據樹的狀態，這種方法可以在任何地方採取同樣的時間作爲第一種方法，和時間作爲第一種方法兩倍之間。

來源

2017-09-15 16:44:53 cdhowie

「*第一種方法是類似於... *： - 如果你使用的是C++的'的std :: MAX（）'函數，但不一定是真實的，如果你使用的是C的'MAX（）'宏是真實的，？B'，這是更接近第二代碼做什麼，除非你很幸運，使用C RTL是[定義'MAX（：這就像'的#define MAX（A，b）（A> b）普遍採用的）'以避免重複調用]（https://stackoverflow.com/questions/5323733/）。 –

時間比較：運營商

回答

相關問題