C++ 19ms


  • 0
    Y
    class Solution 
    {
        public:
        TreeNode* addOneRow(TreeNode* root, int v, int d) 
        {
            queue<TreeNode*> q;
            vector<TreeNode*> row;
            q.push(root);
            
            if(d == 1)
            {
                TreeNode* newRoot = new TreeNode(v);
                newRoot->left = root;
                return newRoot;
            }
            
            // Perform breadth first traversal till we reach the parent row
            while(d > 2)
            {
                queue<TreeNode*> children;
                while(!q.empty())
                {
                    TreeNode* node = q.front();
                    q.pop();
                    if(node->left) { children.push(node->left); }
                    if(node->right) { children.push(node->right); }
                }
                q = children;
                d--;
            }
            // q now contains elements from the parent row of the target
            // Insert row of values `v` as children to all non-null nodes
            while(!q.empty())
            {
                TreeNode* n = q.front();
                if(n)
                {
                    TreeNode* l = new TreeNode(v);
                    TreeNode* r = new TreeNode(v);
                    TreeNode* tempL = n->left;
                    TreeNode* tempR = n->right;
                    n->left = l;
                    n->right = r;
                    l->left = tempL;
                    r->right = tempR;
                }
                q.pop();
            }
            
            return root;
        }
    };
    

Log in to reply
 

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