我看到很多關于樹遍歷的教程，我對有序演算法究竟如何允許我們“爬上”樹感到困惑。
例如，在下面的樹中，我知道我們一直向左走，直到沒有孩子，然后我們附加值。但是演算法中的什么允許我們“爬回”到值為 2 的節點等？
我很難理解這一點。我隨處可見的 Python 演算法是這樣的：
def printInorder(root):
if root:
# First recur on left child
printInorder(root.left)
# then print the data of node
print(root.val),
# now recur on right child
printInorder(root.right)
uj5u.com熱心網友回復：
好吧，讓我從這個角度解釋一下。您知道，一旦列印根節點，您需要對以左子節點為根的子樹和以右子節點為根節點的子樹執行相同的中序遍歷。
我們如何向上遍歷？只是當我們回到遞回呼叫時。是的，這可能會讓人覺得有點奇怪，但這就是函式呼叫的作業方式，一旦被呼叫函式完成，控制元件就會轉到父函式，然后它完成作業，控制元件就會轉到父函式。
現在你問了這個問題，
什么“告訴演算法”我們訪問了節點 1 并且不再向左走
它實際上走到左邊，1基本上不再是一個節點了。只是None現在函式看到你有一個if宣告說do the work only if root is not None。這就是該函式停止進一步呼叫的地方。完成后，它會回傳到它的父級，即1. 現在在1列印1之后，我們再次呼叫遍歷right子級，1但None同樣的事情發生了。然后在節點上1，我們已經完成了我們要求該方法在if塊中執行的所有操作。它回傳到2父節點。
這就是它的作業原理。這張圖將清楚地解釋它：
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/470929.html
上一篇：更改遞回函式內嵌套陣列的值
下一篇：在Java中遞回實作N選擇K