samedi 12 août 2017

What update for a void recursion function

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