遞歸和在二叉樹

Question

繼計數器變量是2碼： 1.查找二叉查找樹的第k個最小整數：

void FindKthSmallest(struct TreeNode* root, int& k) 
{ 
    if (root == NULL) return; 
    if (k == 0) return; // k==0 means target node has been found 
    FindKthSmallest (root->left, k); 

    if (k > 0) // k==0 means target node has been found 
    { 
    k--; 
    if (k == 0) { // target node is current node 
    cout << root->data; 
    return; 
    } else { 
    FindKthSmallest (root->right, k); 
    } 
    } 
} 

查找節點的二進制樹編號：

int Size (struct TreeNode* root) 
{ 
    if (root == NULL) return 0; 
    int l = Size (root->left); 
    int r = Size (root->right); 
    return (l+r+1); 
} 

我的問題： 在這兩個代碼，我會跟蹤我訪問節點的數量。爲什麼是它的代碼1，需要通過引用傳遞一個參數來跟蹤我訪問節點的數量，而代碼2不要求按引用傳遞任何變量？

Answer 1

第一個代碼（1）尋找您的BST最小的節點。您從樹的左側向下搜索，因爲在該位置會找到最小值的節點。您進行多項檢查：

• root == null - 確定樹是否爲空。
• k == 0 - 零在這種情況下是最小的元素。你基於這棵樹的任何原理做出這個假設。

然後，您遞歸遍歷列表以查找樹左側的下一個最小值。你執行一個多檢查，如果你k > 0遞減ķ<-這就是爲什麼你需要通過參考，因爲你正在改變由一個單獨的函數，全局變量等給予一定的價值k傳遞如果k恰好是零，那麼你必須找到最小值的節點，如果不是，則轉到當前節點的右側，然後繼續該過程。這似乎是找到最小的節點非常武斷的方式...

對於第二個代碼（2）你只是在計算節點在你的樹從根開始，計數每個後續節點（或左或右）遞歸直到找不到更多的節點。您返回的結果是左節點，右節點的總數。並且因爲它之前沒有被計數，所以根爲+1。在這種情況下，不需要通過引用變量傳遞，儘管如果您選擇這樣做，您可能會實現一個引用變量。

這是否幫助？

Answer 2

按引用傳遞參數允許你跟蹤遞歸過程中計數的，否則計數將重置。它允許您修改內存空間中的數據，從而更改前一個值而不是當前/本地值。