如何使用遞歸工作遍歷BST？

Question

我理解爲了遍歷BST的概念，但我很困惑它的遞歸如何工作。我很困惑，打印語句和使用root.right作爲參數的遞歸調用將如何運行。我注意到inOder（root.left）將繼續調用以搜索BST中的最低值，但是當它到達null時，if語句無法訪問，因此我們無法跳回到正確的節點。我只想知道我們如何能夠在if語句中達到代碼的底線。

public void inOrder(TreeNode root) { 
    if(root != null) { 
     inOrder(root.left); 
     System.out.printf("%d ",root.data); 
     inOrder(root.right); 
    } 
} 

Answer 1

理解遞歸堆棧很重要。存儲在內存中的單獨方法調用一直沿着左側。打印只有在需要停止的呼叫時纔會啓動。它先打印左邊的孩子，然後打印父母，然後右邊的孩子從左下方打印。