C++ solution using BFS


  • 0
    A

    Using BFS traversal. For each level, use a list to store the nodes in next level. If the next level list is empty, it means the current list already stores all the nodes at the bottom level, return the first node in the list.
    Runtime: O(N)
    Space: O(N)

    class Solution {
    public:
        int findBottomLeftValue(TreeNode* root) {
            list<TreeNode *> nodeList;
            nodeList.push_back(root);
            
            while (!nodeList.empty()) {
                list<TreeNode *> nextList;
                for (auto node : nodeList) {
                    if (node->left) {
                        nextList.push_back(node->left);
                    }
                    if (node->right) {
                        nextList.push_back(node->right);
                    }
                }
                if (nextList.empty()) {
                    return nodeList.front()->val;
                } else {
                    nodeList = nextList;
                }
            }
            return INT_MAX;
        }
    };
    

Log in to reply
 

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