Hi I want to use recursion to find the leftmost value in the last row of the binary tree.
I try to do it in this way:
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;
}
};
The depth can be updated because I return it. However, the lmValue cannot be updated. So the answer is wrong.
I found a solution which do in this way:
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;
}
};
What I lost here is that the solution doesn't return anything, but every variable get updated at each recursion level.
Is that mean if I return nothing, I return everything?
As a newbie, please give me some instructions.
Appreciate!
Aucun commentaire:
Enregistrer un commentaire