1516. 移动 N 叉树的子树 DFS
1516. 移动 N 叉树的子树
给定一棵没有重复值的 N 叉树的根节点
root
,以及其中的两个节点p
和q
。移动节点
p
及其子树,使节点p
成为节点q
的直接子节点。如果p
已经是q
的直接子节点,则请勿改动任何节点。节点p
必须是节点q
的子节点列表的最后一项。返回改动后的树的根节点。
节点
p
和q
可能是下列三种情况之一:
- 节点
q
在节点p
的子树中。- 节点
p
在节点q
的子树中。- 节点
p
不在节点q
的子树中,且节点q
也不在节点p
的子树中。在第 2 种和第 3 种情况中,你只需要移动
p
(及其子树),使p
成为q
的子节点。但是在第 1 种情况中,树的节点可能会断连,因此你还需要重新连接这些节点。请在解题前仔细阅读示例。N 叉树的输入序列以层序遍历的形式给出,每组子节点用 null 分隔(见示例)。
例如,上面的树会被序列化为 [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]。
示例 1:
输入: root = [1,null,2,3,null,4,5,null,6,null,7,8], p = 4, q = 1 输出: [1,null,2,3,4,null,5,null,6,null,7,8] 解释: 该示例属于第二种情况,节点 p 在节点 q 的子树中。我们可以移动节点 p 及其子树,使 p 成为节点 q 的直接子节点。 注意,节点 4 是节点 1 的最后一个子节点。示例 2:
输入: root = [1,null,2,3,null,4,5,null,6,null,7,8], p = 7, q = 4 输出: [1,null,2,3,null,4,5,null,6,null,7,8] 解释: 节点 7 已经是节点 4 的直接子节点,因此我们不改动任何节点。示例 3:
输入: root = [1,null,2,3,null,4,5,null,6,null,7,8], p = 3, q = 8 输出: [1,null,2,null,4,5,null,7,8,null,null,null,3,null,6] 解释: 该示例属于第三种情况,节点 p 不在节点 q 的子树中,反之亦然。我们可以移动节点 3 及其子树,使之成为节点 8 的子节点。提示:
- 节点的总数在
[2, 1000]
间。- 每个节点都有 唯一 的值。
p != null
q != null
p
和q
是两个不同的节点(即p != q
)。原文链接
做题结果
成功。这题难的地方是最复杂的情况一没有示例。
补充情况一说明:
如果p是q的直接、间接父节点,则把pq从树中断开,q放在原本p的位置,p放在q的最后一个节点(p中原本为q的部分已断开)
方法:DFS
1. 找到 p 和 q 的关系,找到他们的父节点pParent和qParent
2. 如果p是q的父节点,则需要断开q,q从父节点移除,q放在本来p的位置
3. p需要重父节点移除,然后放到q的最后一个子节点
class Solution {
Node pParent;
Node qParent;
public Node moveSubTree(Node root, Node p, Node q) {
Node pre = new Node(0);
pre.children = new ArrayList<>();
pre.children.add(root);
fillTime(pre,p,q);
//1.q 是 p 的直接父类
if(pParent==q) return root;
//2.p 是 q 的间接、直接父类
int id = pParent.children.indexOf(p);
pParent.children.remove(p);
if(isParent(p,q)){
qParent.children.remove(q);
pParent.children.add(id,q);
}
q.children.add(p);
return pre.children.get(0);
}
private boolean isParent(Node p,Node q){
for(Node item:p.children){
if(item==q || isParent(item,q)) return true;
}
return false;
}
private void fillTime(Node root,Node p,Node q){
if(root.children!=null){
for(Node next:root.children){
if(next==p) pParent=root;
if(next==q) qParent=root;
fillTime(next,p,q);
}
}
}
}