513. Find Bottom Left Tree Value

class Solution 
{
private:
    int getDepth(TreeNode *i_root)
    {
        if(!i_root) return 0;
        
        return 1 + max(getDepth(i_root->left), getDepth(i_root->right));
    }
public:
    // int findBottomLeftValue(TreeNode* root)
    int findBottomLeftValue(TreeNode *i_root) 
    {
        int result = 0;
        auto iter = i_root;
        while(true)
        {
            if(getDepth(iter) == 1) // we find the leaf
            {
                result = iter->val;
                break;
            }
            
            // getDepth has lots of duplicate work, so it is slow
            iter = (getDepth(iter->left) >= getDepth(iter->right) ? iter->left : iter->right);
        }
        
        return result;
    }
};

class Solution 
{
public:
    // int findBottomLeftValue(TreeNode* root)
    int findBottomLeftValue(TreeNode *i_root) 
    {
        int result = i_root->val; // the note says i_root is not nullptr
        queue<const TreeNode *> currentLevelNodes{{i_root}};
        queue<const TreeNode *> nextLevelNodes;
        
        while(!currentLevelNodes.empty() || !nextLevelNodes.empty())
        {
            if(currentLevelNodes.empty())
            {
                swap(currentLevelNodes, nextLevelNodes);
                
                result = currentLevelNodes.front()->val;
            }
            else
            {
                auto node = currentLevelNodes.front();
                currentLevelNodes.pop();
                
                if(node->left) nextLevelNodes.push(node->left);
                if(node->right) nextLevelNodes.push(node->right);
            }
        }
        
        return result;
    }
};

class Solution 
{
private:
    int result = 0, deepestDepth = 0;
    
    void findBottomLeftValue(TreeNode *i_root, int depth)
    {
        // since the recursion order is left->right, the first node reach the new level is the last level's most left node
        if(deepestDepth < depth) 
        {
            result = i_root->val;
            deepestDepth = depth;
        }
        
        if(i_root->left) findBottomLeftValue(i_root->left, depth + 1);
        if(i_root->right) findBottomLeftValue(i_root->right, depth + 1);
    }
public:
    // int findBottomLeftValue(TreeNode* root)
    int findBottomLeftValue(TreeNode *i_root) 
    {
        findBottomLeftValue(i_root, 1);
        
        return result;
    }
};