C++ solution, queue and no special marker (like NULL)


  • 0
    P

    No sentinel/special marker, just track the first parent node of each level. Use that to identify start-of-next-level/end-of-last-level.

    vector<vector<int>> levelOrder(TreeNode* root) {
            deque<TreeNode*> queue;
            vector<vector<int>> order;
            if (root) {
                //Queue for usual level-order/BFS on tree
                queue.push_back(root);
                //Single extra variable to keep track of the firstParent at previous level, this will help determine the end of a level
                TreeNode *firstParent = root;
                vector<int> currentLevel;
                while (!queue.empty()) {
                    TreeNode *node = queue.front();
                    queue.pop_front();
                    const bool endOfPrevLevel = firstParent && (firstParent->left? firstParent->left == node : firstParent->right == node );
                    if (endOfPrevLevel) {
                        //End of prev level, wrap up that level and reset for this new level (of which "node" is first level)
                        order.push_back(currentLevel);
                        currentLevel.clear();
                        firstParent = NULL;
                    }
                    //Track first parent at each level, only if not already set
                    if (!firstParent && (node->left || node->right))
                        firstParent = node;
                    //Usual book-keeping for level order
                    currentLevel.push_back(node->val);
                    if (node->left)
                        queue.push_back(node->left);
                    if (node->right)
                        queue.push_back(node->right);
                    
                }
                if (!currentLevel.empty())
                    order.push_back(currentLevel);
            }
            return order;
        }
    

Log in to reply
 

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