TreeNode* addOneRow(TreeNode* root, int val, int depth) {

if (!root) {

return root;

}

if (depth > 2) {

addOneRow(root->left, val, depth - 1);

addOneRow(root->right, val, depth - 1);

} else if (depth == 2) {

root->left = new TreeNode(val, root->left, NULL);

root->right = new TreeNode(val, NULL, root->right);

} else { // depth == 1

root = new TreeNode(val, root, NULL);;

}

return root;

}