?

給定一個二叉樹，根節點為第1層，深度為 1。在其第?d?層追加一行值為?v?的節點。

添加規則：給定一個深度值?d?（正整數），針對深度為?d-1?層的每一非空節點?N，為?N?創建兩個值為?v?的左子樹和右子樹。

將?N?原先的左子樹，連接為新節點?v?的左子樹；將?N?原先的右子樹，連接為新節點?v?的右子樹。

如果?d?的值為 1，深度 d - 1 不存在，則創建一個新的根節點?v，原先的整棵樹將作為?v?的左子樹。

示例 1:

輸入: 
二叉樹如下所示:4/   \2     6/ \   / 3   1 5   v = 1d = 2輸出: 4/ \1   1/     \2       6/ \     / 3   1   5   

示例 2:

輸入: 
二叉樹如下所示:4/   2    / \   3   1    v = 1d = 3輸出: 4/   2/ \    1   1/     \  
3       1

注意:

1. 輸入的深度值 d 的范圍是：[1，二叉樹最大深度 + 1]。
2. 輸入的二叉樹至少有一個節點。

class Solution {
public:TreeNode* addOneRow(TreeNode* root, int v, int d) {if(!root) return root;if(d == 1){TreeNode *temp = new TreeNode(v);temp->left = root;temp->right = NULL;return temp;}queue<TreeNode *> qu;qu.push(root);int n = 0;while(!qu.empty()){int count = qu.size();++n;while(count--){TreeNode *s = qu.front();qu.pop();if(n == d -1){TreeNode *temp1 = new TreeNode(v);temp1->left = s->left;temp1->right = NULL;s->left = temp1;TreeNode *temp2 = new TreeNode(v);temp2->right = s->right;temp2->left = NULL;s->right = temp2;}if(s->left) qu.push(s->left);if(s->right) qu.push(s->right);}}return root;}
};

?

?