前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode 623. 在二叉树中增加一行(BFS/DFS)

LeetCode 623. 在二叉树中增加一行(BFS/DFS)

作者头像
Michael阿明
发布2020-07-13 17:05:58
6220
发布2020-07-13 17:05:58
举报
文章被收录于专栏:Michael阿明学习之路

1. 题目

给定一个二叉树,根节点为第1层,深度为 1。在其第 d 层追加一行值为 v 的节点。

添加规则:给定一个深度值 d (正整数),针对深度为 d-1 层的每一非空节点 N,为 N 创建两个值为 v 的左子树和右子树。

将 N 原先的左子树,连接为新节点 v 的左子树;将 N 原先的右子树,连接为新节点 v 的右子树。

如果 d 的值为 1,深度 d - 1 不存在,则创建一个新的根节点 v,原先的整棵树将作为 v 的左子树。

代码语言:javascript
复制
示例 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

用队列按层遍历,到达指定的层,在层间加入新的节点,再将新节点与上下层连接起来

代码语言:javascript
复制
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;
    }
};
在这里插入图片描述
在这里插入图片描述

2.2 DFS

代码语言:javascript
复制
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);
    }
};
在这里插入图片描述
在这里插入图片描述
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019/12/21 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1. 题目
  • 2. 解题
    • 2.1 BFS
      • 2.2 DFS
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档