Non recursive 8ms solution with helper function


  • 0
    L
    /**
     * Definition for binary tree
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        vector<vector<int> > levelOrder(TreeNode *root) {
            vector<vector<int>> answer;
            if (root == nullptr)
                return answer;
            queue<TreeNode*>        myQueue;
            myQueue.push(root);
            while (!myQueue.empty())
            {
                myQueue.push(nullptr);
                answer.push_back(GetNextRow(myQueue));   
                myQueue.pop();
            }
            return answer;
        }
        
        vector<int> GetNextRow(queue<TreeNode*>& myQueue)
        {
            vector<int> nextRow;
            if (myQueue.empty())
                return nextRow;
            while (myQueue.front() != nullptr)
            {
                TreeNode*       currentNode = myQueue.front();
                myQueue.pop();
                if (currentNode->left != nullptr)
                    myQueue.push(currentNode->left);
                if (currentNode->right != nullptr)
                    myQueue.push(currentNode->right);
                nextRow.push_back(currentNode->val);
            }
            return nextRow;
        }
    };
    

    Helper function populates the next level into the solution. Uses breadth first search with a queue. Levels are delineated by the nullptr.


Log in to reply
 

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