確定一棵樹是否爲單一樹的時間複雜度？

Question

最近，我碰到這個問題一提出二叉樹：

1. 鑑於一些任意的非平衡樹，什麼大-O，以確定它是否是單值（所有元素都是相同的值） 。

2. 這會在上述情況下導致最壞的大O複雜度，一個平衡的 樹或線性樹？

這是我的問題的答案：

1. 如果要判斷一棵樹是同值，我們必須檢查每個節點。所以，複雜度是O（n）。

2. 無論是線性樹還是平衡樹，如果它們具有相同數量的節點，則會有相同數量的比較。所以，複雜性會一樣。

這是正確的嗎？

Answer 1

如果您得到一個任意的二叉樹，在最壞的情況下，您必須檢查所有節點以確定它們是否具有相同的值。在這裏可以使用一個簡單的對抗論據 - 如果你的算法沒有看所有的值，因爲樹中任何不同的值之間沒有關係，敵人可以給你一棵樹，其中n-1個值都是相同的。如果你沒有看到最後一個值，攻擊者可以通過將該值設置爲與算法所說的相反來強制你的算法出錯。

在另一方面，如果你在談論一個二進制搜索樹，那麼您可以在時間O（h）時，其中h是樹的高度解決這個問題。具體來說，只要看看第一個和最後一個值，看看它們是否相同。如果是這樣，樹中的所有中間值必須相同。如果他們不是，那麼你目睹了兩個不同的價值觀。這將在完美平衡的樹上運行O（log n），並在退化鏈表上運行O（n）。我懷疑這可能是原始問題所要求的，因爲這是一個比一般二叉樹案更有趣的問題（至少在我看來）。

希望這會有所幫助！