河北住房与城乡建设厅网站,佛山网站策划公司,山东网站建设哪家便宜,asp网站开发实例pdf文章目录1. 题目2. 解题2.1 BFS2.2 DFS1. 题目
给定一个二叉树#xff0c;根节点为第1层#xff0c;深度为 1。在其第 d 层追加一行值为 v 的节点。
添加规则#xff1a;给定一个深度值 d #xff08;正整数#xff09;#xff0c;针对深度为 d-1 层的每一非空节点 N根节点为第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 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]。
输入的二叉树至少有一个节点。来源力扣LeetCode 链接https://leetcode-cn.com/problems/add-one-row-to-tree 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
2.1 BFS
用队列按层遍历到达指定的层在层间加入新的节点再将新节点与上下层连接起来
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;queueTreeNode* 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;//存储下层节点leftr tp-right;//存储下层节点righttp-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;}
};2.2 DFS
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,deep1,d,v);dfs(root-right,deep1,d,v);}
};
