C recursive and O(n)


  • 1
    L
    int get_height (struct TreeNode* root, struct TreeNode** bottom_left, int level, int *max_level) {
        if (root == NULL) {
            return 0;
        }
    
        // if leaf at lowest level we've seen, store it as bottom_left node
        if (root->left == NULL && root->right == NULL && level > *max_level)
            *bottom_left = root;
    
        if (level > *max_level)
            *max_level = level;
    
        int left = 1 + get_height (root->left, bottom_left, level + 1, max_level);
        int right = 1 + get_height (root->right, bottom_left, level + 1, max_level);
        if (left >= right) {
            return left;
        } else {
            return right;
        }
    } 
    
    int findBottomLeftValue(struct TreeNode* root) {
        int max_level = -1;
        struct TreeNode *bottom_left = NULL;    
        get_height (root, &bottom_left, 0, &max_level);
        
        return bottom_left->val;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.