[C++] Simple level order traversal solution


  • 0
    V

    When you reach the d-th level create new nodes and add them to the tree, and return the root. If not yet at the d-th level, add nodes to a queue in the level order.

    Self-explanatory solution.

    class Solution {
    public:
        TreeNode* addOneRow(TreeNode* root, int v, int d) {
            if(d == 1){
                TreeNode* node = new TreeNode(v);
                node->left = root;
                return node;
            }
            
            queue<TreeNode*> Q;
            Q.push(root);
            while(d>1){
                d--;
                int n = Q.size();
                for(int i=0; i<n; i++){
                    TreeNode* node = Q.front();
                    Q.pop();
                    if(d == 1){ 
                        // We have found the level where we have to add new nodes
                        TreeNode* temp = new TreeNode(v);
                        temp->left = node->left;
                        node->left = temp;
                        
                        temp = new TreeNode(v);
                        temp->right = node->right;
                        node->right = temp;
                    }
                    else{
                        if(node->left != NULL) Q.push(node->left);
                        if(node->right != NULL) Q.push(node->right);
                    }
                }
            }
            return root;
        }
    };
    

Log in to reply
 

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