Add One Row to Tree

用bfs, 一旦走到目標的前一層就跳出, 然後再目標的每個節點, 都把他們的左子樹給切出來, 換上一個新的節點, 再把原本的左子樹黏到這個節點的左子樹, 即可, 要注意當d == 1, 就是新增一個root, 並把原本的樹黏到這個新root的左子樹

class Solution {
public:
    TreeNode* addOneRow(TreeNode* root, int v, int d) {
        if(!root) return root;
        if(d == 1){
            TreeNode *new_root = new TreeNode(v);
            new_root->left = root;
            return new_root;
        }
        queue<TreeNode *> q;
        q.push(root);
        int depth = 1;
        while(!q.empty() && depth != d - 1){
          int len = q.size();
          for(int i = 0; i < len; i++){
            TreeNode *cur = q.front();
            q.pop();
            if(cur->left){
              q.push(cur->left);
            }
            if(cur->right){
              q.push(cur->right);
            }
          }
          depth++;
        }
        int len = q.size();
        for(int i = 0; i < len; i++){
          TreeNode *cur = q.front();
          q.pop();
TreeNode *newl = new TreeNode(v);
          TreeNode *tmpl = cur->left;
          cur->left = newl;
          newl->left = tmpl;
TreeNode *newr = new TreeNode(v);
          TreeNode *tmpr = cur->right;
          cur->right = newr;
          newr->right = tmpr;
        }
        return root;
    }
};