LeetCode 623. 在二叉树中增加一行（BFS/DFS）

示例 1:
输入: 
二叉树如下所示:
       4
     /   \
    2     6
   / \   / 
  3   1 5   

v = 1
d = 2

输出: 
       4
      / \
     1   1
    /     \
   2       6
  / \     / 
 3   1   5   

示例 2:
输入: 
二叉树如下所示:
      4
     /   
    2    
   / \   
  3   1    

v = 1
d = 3

输出: 
      4
     /   
    2
   / \    
  1   1
 /     \  
3       1
注意:
输入的深度值 d 的范围是：[1，二叉树最大深度 + 1]。
输入的二叉树至少有一个节点。

class Solution {
public:
    TreeNode* addOneRow(TreeNode* root, int v, int d) {
        if(d == 1)
        {
        	TreeNode *newRoot = new TreeNode(v);
        	newRoot->left = root;
        	return newRoot;
        }
        int deep = 1, n;
        queue<TreeNode*> q;
        TreeNode *tp, *l, *r;
        q.push(root);
        while(!q.empty() && deep < d)
        {
        	n = q.size();
        	while(n--)
        	{
	        	tp = q.front();
    	    	q.pop();
    	    	if(deep == d-1)	//到达指定的层了
    	    	{
    	    		l = tp->left;//存储下层节点left
    	    		r= tp->right;//存储下层节点right
    	    		tp->left = new TreeNode(v);//新节点
    	    		tp->right = new TreeNode(v);
    	    		tp->left->left = l;//新节点与下层连接上
    	    		tp->right->right = r;
    	    	}
    	    	if(tp->left)
    	    		q.push(tp->left);
    	    	if(tp->right)
    	    		q.push(tp->right);
    	    }
    	    deep++;
        }
        return root;
    }
};

class Solution {
public:
    TreeNode* addOneRow(TreeNode* root, int v, int d) {
        if(d == 1)
        {
        	TreeNode *newRoot = new TreeNode(v);
        	newRoot->left = root;
        	return newRoot;
        }
        dfs(root,1,d,v);
        return root;
    }

    void dfs(TreeNode* root, int deep, int &d, int &v)
    {
    	if(!root || deep == d)
    		return;
    	if(deep == d-1)
    	{
    		TreeNode* l = root->left;
    		TreeNode* r = root->right;
    		root->left = new TreeNode(v);
    		root->right = new TreeNode(v);
    		root->left->left = l;
    		root->right->right = r;
    	}
    	dfs(root->left,deep+1,d,v);
    	dfs(root->right,deep+1,d,v);
    }
};