An easy to understand BFS method with C++


  • 0
    S
     vector<vector<int>> levelOrderBottom(TreeNode* root) {
            std::vector<std::vector<int>> values;
            if (root == nullptr)
                return values;
            std::queue<TreeNode*> q;
            q.push(root);
            q.push(nullptr); // indicate the finish of a level
            values.push_back(std::vector<int>());
            while (true){
                auto p = q.front();
                q.pop();
                if (p == nullptr){
                    if (q.empty()) // this is the last nullptr indicating the ending of the last level
                        break;
                    q.push(nullptr);
                    values.push_back(std::vector<int>());
                }else{
                    values.back().push_back(p->val);
                    if (p->left != nullptr)
                        q.push(p->left);
                    if (p->right != nullptr)
                        q.push(p->right);
                }
            }
            std::reverse(values.begin(), values.end());
            return values;
        }
    

Log in to reply
 

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