什麼更新爲無效遞歸函數

Question

您好我想使用遞歸找到最左邊的二進制樹的行中的值。

我嘗試做了這種方式：

class Solution { 

public: 
    int findBottomLeftValue(TreeNode* root) { 
     int lmValue = root -> val; 
     int Maxdepth = 0; 
     Maxdepth = helper(root, 0, Maxdepth, lmValue); 
     cout << Maxdepth; 
     return lmValue; 

    } 

private: 
    int helper(TreeNode* root, int depth, int Maxdepth, int lmValue) { 
     if (!root) 
      return depth; 

     int leftDepth = helper(root -> left, depth + 1, Maxdepth, lmValue); 
     int rightDepth = helper(root -> right, depth + 1, Maxdepth, lmValue); 

     int curDepth = max(leftDepth, rightDepth); 
     if (curDepth > Maxdepth) { 
      Maxdepth = curDepth; 
      lmValue = root -> val; 
     } 

     return Maxdepth; 

    } 
}; 

深度可以，因爲我回來就馬上更新。但是，lmValue無法更新。所以答案是錯誤的。

我發現裏面做這樣的解決方案：

class Solution { 
public: 
    void findBottomLeftValue(TreeNode* root, int& maxDepth, int& leftVal, int depth) { 
     if (root == NULL) { 
      return; 
     } 
     //Go to the left and right of each node 
     findBottomLeftValue(root->left, maxDepth, leftVal, depth+1); 
     findBottomLeftValue(root->right, maxDepth, leftVal, depth+1); 

     //Update leftVal and maxDepth 
     if (depth > maxDepth) { 
      maxDepth = depth; 
      leftVal = root->val; 
     } 
    } 

    //Entry function 
    int findBottomLeftValue(TreeNode* root) { 
     int maxDepth = 0; 
     //Initialize leftVal with root's value to cover the edge case with single node 
     int leftVal = root->val; 
     findBottomLeftValue(root, maxDepth, leftVal, 0); 
     return leftVal; 
    } 
}; 

我失去了在這裏是該解決方案不返回任何東西，但每個變量獲得在每個遞歸級別更新。

這就是說，如果我什麼都不返回，我會返回一切？

作爲新手，請給我一些指示。

感謝！

Answer 1

這是一個非常寬泛的問題，但我會盡我所能給你一個總結。

void findBottomLeftValue(TreeNode* root, int& maxDepth, int& leftVal, int depth) { 
    // (Recursive calls removed, not relevant to this discussion...) 
    if (depth > maxDepth) { 
     maxDepth = depth; 
     leftVal = root->val; 
    } 
} 

在所述類型的前部的&意味着你通過引用傳遞變量。變量maxDepth和leftVal未被複制到該函數中，因此對這些變量的賦值將反映在原始值中。這是pre-C++ 11代碼中從函數返回多個值的常見習慣用法。這是一個更簡單的例子。

void by_value(int x) { 
    x++; 
} 
void by_reference(int& x) { 
    x++; 
} 
int main() { 
    int var = 0; 
    cout << var << endl; // Prints 0 
    by_value(var); 
    cout << var << endl; // Prints 0, since the value was copied to the function 
    by_reference(var); 
    cout << var << endl; // Prints 1, since the value was passed by reference 
         // so the changes in the function are reflected in the 
         // caller 
}