Intuition Use queues to peform bfs and traverse the tree. When you reach depth - 1 , perform the operations mentioned in the question Approach There are two cases when you reach depth - 1 using bfs. Assume curr is the current node at depth - 1 * curr->left != NULL * curr->left == NULL The code handles the above two cases.
| 27 | So we have to write a seperate code to handle depth = 1 case. |
| 28 | */ |
| 29 | TreeNode* addOneRow(TreeNode* root, int val, int depth) { |
| 30 | |
| 31 | int d = 0; |
| 32 | if(d == (depth - 1)){ |
| 33 | TreeNode *new_node = new TreeNode(val); |
| 34 | new_node->left = root; |
| 35 | root = new_node; |
| 36 | return root; |
| 37 | } |
| 38 | queue<TreeNode*> q; |
| 39 | q.push(root); |
| 40 | while(!q.empty()){ |
| 41 | int size = q.size(); |
| 42 | d++; |
| 43 | for(int i=0;i<size;i++){ |
| 44 | TreeNode *curr = q.front(); |
| 45 | q.pop(); |
| 46 | if(!curr) |
| 47 | continue; |
| 48 | if(d == (depth - 1)){ |
| 49 | TreeNode *new_node = new TreeNode(val); |
| 50 | TreeNode *new_node1 = new TreeNode(val); |
| 51 | if(curr->left){ |
| 52 | TreeNode *temp = curr->left; |
| 53 | new_node->left = temp; |
| 54 | curr->left = new_node; |
| 55 | } |
| 56 | else{ |
| 57 | curr->left = new_node; |
| 58 | } |
| 59 | if(curr->right){ |
| 60 | TreeNode *temp = curr->right; |
| 61 | new_node1->right = temp; |
| 62 | curr->right = new_node1; |
| 63 | } |
| 64 | else{ |
| 65 | curr->right = new_node1; |
| 66 | } |
| 67 | |
| 68 | } |
| 69 | if(curr->left) |
| 70 | q.push(curr->left); |
| 71 | if(curr->right) |
| 72 | q.push(curr->right); |
| 73 | |
| 74 | } |
| 75 | if(d == (depth-1)) |
| 76 | break; |
| 77 | } |
| 78 | return root; |
| 79 | } |
| 80 | ======= |
| 81 | /* |
| 82 |