二叉樹

Question

算法的通用遍歷的時間複雜度：

Tour (node t) 
if t is a leaf node 
    visit t 
else 
    visit t 
    Tour(t.left) 
    visit t 
    Tour(t.right) 
    visit t 

是代碼的上述O（n）的複雜性？ ;其中n是節點的數量。

Answer 1

是的，每個節點都訪問一次，訪問時間不變。我假設你在其他條款中只有一個visit的意思，而不是3。這使我更有意義：

Tour (node t) 
    visit t 
    if t is a leaf node 
     return 
    Tour(t.left) 
    Tour(t.right) 

Answer 2

問：什麼是您的光臨T速度？

如果您的訪問操作是恆定時間操作並且不依賴於輸入大小n，則該算法的總體時間複雜度爲O（n）。