LeetCode——623.在二叉树中增加一行

时间:2023-09-02 22:17:17
LeetCode——623.在二叉树中增加一行

给定一个二叉树,根节点为第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

这道题让我们给二叉树增加一行,给了需要增加的值,还有需要增加的位置深度,题目中给的例子也比较能清晰的说明问题。但是漏了一种情况,那就是当d=1时,这该怎么加?这时候就需要替换根结点了。其他情况的处理方法都一样,这里博主第一映像觉得应该用层序遍历来做,每遍历完一层,d自减1,当d==1时,需要对于当前层的每一个结点,先用临时变量保存其原有的左右子结点,然后新建值为v的左右子结点,将原有的左子结点连到新建的左子结点的左子结点上,将原有的右子结点连到新建的右子结点的右子结点,是不是很绕-.-|||。如果d不为1,那么就是层序遍历原有的排入队列操作,记得当检测到d为0时,直接返回,因为添加操作已经完成,没有必要遍历完剩下的结点,参见代码如下:

解法一:

class Solution {
public:
TreeNode* addOneRow(TreeNode* root, int v, int d) {
if (!root) return NULL;
if (d == 1) {
TreeNode *newRoot = new TreeNode(v);
newRoot->left = root;
return newRoot;
}
queue<TreeNode*> q{{root}};
while (!q.empty()) {
if (--d == 0) return root;
int n = q.size();
for (int i = 0; i < n; ++i) {
auto t = q.front(); q.pop();
if (d == 1) {
TreeNode *left = t->left;
TreeNode *right = t->right;
t->left = new TreeNode(v);
t->right = new TreeNode(v);
t->left->left = left;
t->right->right = right;
} else {
if (t->left) q.push(t->left);
if (t->right) q.push(t->right);
}
}
}
return root;
}
};

虽然博主一贯的理念是二叉树问题肯定首选递归来解,但是这道题博主刚开始以为递归没法解,结果看了大神们的帖子,才发现自己还是图样图森破,难道二叉树的问题皆可递归?反正这道题是可以的,而且写法 so 简洁,乍一看上去,会有疑问,题目中明明d的范围是从1开始的,为何要考虑d为0的情况,后来读懂了整个解法后,才为原作者的聪慧叹服。这里d的0和1,其实相当于一种 flag,如果d为1的话,那么将 root 连到新建的结点的左子结点上;反之如果d为0,那么将 root 连到新建的结点的右子结点上,然后返回新建的结点。如果 root 存在且d大于1的话,那么对 root 的左子结点调用递归函数,注意此时若d的值正好为2,那么就不能直接减1,而是根据左右子结点的情况分别赋值1和0,这样才能起到 flag 的作用嘛,叼的飞起,参见代码如下:

解法二:

class Solution {
public:
TreeNode* addOneRow(TreeNode* root, int v, int d) {
if (d == 0 || d == 1) {
TreeNode *newRoot = new TreeNode(v);
(d ? newRoot->left : newRoot->right) = root;
return newRoot;
}
if (root && d > 1) {
root->left = addOneRow(root->left, v, d > 2 ? d - 1 : 1);
root->right = addOneRow(root->right, v, d > 2 ? d - 1 : 0);
}
return root;
}
};

方法一:深度优先搜索(递归)

如果 d 的值为 1,我们就添加一个节点,并将整棵树作为新节点的左子树。否则我们可以使用深度优先搜索找出所有 d 层的节点并进行操作。在搜索时,我们需要记录当前节点的深度 depth,如果此时 depth == d - 1,那么我们需要在当前节点的左右孩子各增加一个节点。如果当前节点的左右孩子已经有节点,我们就将这些节点存储到临时变量中,在增加新节点后再把左右孩子作为新节点的左子树或右子树,并结束递归。如果 depth != d - 1,我们就需要对当前节点的子节点进行递归搜索。

java

public class Solution {
public TreeNode addOneRow(TreeNode t, int v, int d) {
if (d == 1) {
TreeNode n = new TreeNode(v);
n.left = t;
return n;
}
insert(v, t, 1, d);
return t;
} public void insert(int val, TreeNode node, int depth, int n) {
if (node == null)
return;
if (depth == n - 1) {
TreeNode t = node.left;
node.left = new TreeNode(val);
node.left.left = t;
t = node.right;
node.right = new TreeNode(val);
node.right.right = t;
} else {
insert(val, node.left, depth + 1, n);
insert(val, node.right, depth + 1, n);
}
}
}

复杂度分析

时间复杂度:O(N),其中 N 是二叉树的节点个数。我们最多会遍历 N 个节点。

空间复杂度:O(N)。在最坏情况下,需要递归 N 层,用到 O(N) 的栈空间。

方法二:深度优先搜索(非递归)

我们可以直接用栈来模拟递归,实现深度优先搜索的非递归版本。

我们首先将根节点入栈,随后每次栈顶的元素即为当前搜索到的结点,我们取出这个节点,根据 depth 和 d - 1 的关系为当前节点增加新的子节点,或者将当前节点的子节点全部入栈,继续搜索。

java

public class Solution {
class Node{
Node(TreeNode n,int d){
node=n;
depth=d;
}
TreeNode node;
int depth;
}
public TreeNode addOneRow(TreeNode t, int v, int d) {
if (d == 1) {
TreeNode n = new TreeNode(v);
n.left = t;
return n;
}
Stack<Node> stack=new Stack<>();
stack.push(new Node(t,1));
while(!stack.isEmpty())
{
Node n=stack.pop();
if(n.node==null)
continue;
if (n.depth == d - 1 ) {
TreeNode temp = n.node.left;
n.node.left = new TreeNode(v);
n.node.left.left = temp;
temp = n.node.right;
n.node.right = new TreeNode(v);
n.node.right.right = temp; } else{
stack.push(new Node(n.node.left, n.depth + 1));
stack.push(new Node(n.node.right, n.depth + 1));
}
}
return t;
}
}

复杂度分析

时间复杂度:O(N),其中 N 是二叉树的节点个数。我们最多会遍历 N 个节点。

空间复杂度:O(N)。

方法三:广度优先搜索

我们同样可以使用广度优先搜索解决这个问题,并且广度优先搜索是最容易理解且最直观的一种方法。

我们将根节点放入队列 queue。在每一轮搜索中,如果 queue 中节点的深度为 d - 1(显然 queue 中所有的节点都在同一深度),我们就退出搜索,并为 queue 中所有节点添加新的子节点;否则我们将 queue 中所有节点的子节点放入新的队列 temp 中,再用 temp 替代 queue。

java

public class Solution {
public TreeNode addOneRow(TreeNode t, int v, int d) {
if (d == 1) {
TreeNode n = new TreeNode(v);
n.left = t;
return n;
}
Queue < TreeNode > queue = new LinkedList < > ();
queue.add(t);
int depth = 1;
while (depth < d - 1) {
Queue < TreeNode > temp = new LinkedList < > ();
while (!queue.isEmpty()) {
TreeNode node = queue.remove();
if (node.left != null) temp.add(node.left);
if (node.right != null) temp.add(node.right);
}
queue = temp;
depth++;
}
while (!queue.isEmpty()) {
TreeNode node = queue.remove();
TreeNode temp = node.left;
node.left = new TreeNode(v);
node.left.left = temp;
temp = node.right;
node.right = new TreeNode(v);
node.right.right = temp;
}
return t;
}
}

复杂度分析

时间复杂度:O(N),其中 NN 是二叉树的节点个数。我们最多会遍历 N 个节点。

空间复杂度:O(N)。

按层递归遍历到目标层的前一层按规则直接改树,注意第一层是边界,需要单独输出。

python

class Solution:
def addOneRow(self, root: TreeNode, v: int, d: int) -> TreeNode:
if d == 1:
r = TreeNode(v)
r.left = root
return r
def f(r, i):
if r:
if i < d-1:
f(r.left, i + 1)
f(r.right, i + 1)
else:
t = TreeNode(v)
t.left = r.left
r.left = t
t = TreeNode(v)
t.right = r.right
r.right = t
f(root, 1)
return root