我正在復習 leet 代碼樹問題，Python 型別問題中二叉樹的迭代后序遍歷的每個解決方案似乎都使??用遞回。
由于python中沒有尾遞回，我相信迭代演算法更快，因為在堆疊中移動比跳過堆疊呼叫幀花費的時間更少。
此外，我相信迭代方法使用的記憶體更少，因為僅跟蹤一個堆疊占用的空間比遞回呼叫幀堆疊占用的空間少。
我了解后序迭代遍歷的典型方法需要 2 個堆疊和 while 回圈，因此它似乎很復雜。
但是，有一種演算法只使用 1 個堆疊和 while 回圈。
這里是：
def postorderIterative(root):
curr = root
stack = []
while current or stack:
if current:
stack.append[current]
current = current.left
else:
tmp = stack[-1].right
if not tmp:
tmp = stack.pop()
#process postorder here
while stack and tmp == stack[-1].right:
tmp = stack.pop()
#process postorder here
else:
current = tmp
信用和解釋到這里
即使迭代更好，大多數視頻解決方案似乎比迭代更多地使用遞回后序遍歷，是否有任何理由？是因為遞回更容易理解嗎？
似乎對于足夠大的測驗用例，遞回可能會在任何呼叫中失敗，所以我傾向于總是進行迭代。這是一種有效的方法嗎？
我真的找不到 leet 代碼的迭代解決方案視頻：543. 二叉樹的直徑
這些都是遞回的，因此不是最優的，即使他們說它是最優的。
如果我錯了，請告訴我為什么。如果不。也請告訴我。我是來學習的！
uj5u.com熱心網友回復：
迭代和遞回實作都具有相同的時間和空間復雜度。就大 O 而言，運行時間的差異是微不足道的。說到最優，人們通常指的是時間/空間復雜度是最優的。
其次，呼叫堆疊限制只會成為高度達到數百的二叉樹的問題。如果這樣高度的樹是平衡的，它的節點將比宇宙中的原子還多。因此，只有當二叉樹嚴重傾斜時，我們才會遇到堆疊限制，這對于現實生活中的問題來說毫無用處。簡而言之，我不認為呼叫堆疊限制在這里是一個如此重要的論點。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/523498.html
標籤：递归树迭代运行后购
下一篇：作為gnuplot中的引數的函式