"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children if children is not None else []
"""
class Solution:
def moveSubTree(self, root: 'Node', p: 'Node', q: 'Node') -> 'Node':
# Helper: find parent and node mapping
parent = {}
def dfs(node, par):
if node:
parent[node] = par
for child in node.children:
dfs(child, node)
dfs(root, None)
# If q is a descendant of p, moving p under q creates a cycle.
# So we need to check if q is in p's subtree.
def is_descendant(node, target):
if node == target:
return True
for child in node.children:
if is_descendant(child, target):
return True
return False
if is_descendant(p, q):
# Remove q from its parent
par_q = parent[q]
if par_q:
par_q.children = [c for c in par_q.children if c != q]
# Remove p from its parent
par_p = parent[p]
if par_p:
par_p.children = [c for c in par_p.children if c != p]
# Insert q as a child of p
p.children.append(q)
# If q was root, p is new root
return p if root == q else root
else:
# Remove p from its parent
par_p = parent[p]
if par_p:
par_p.children = [c for c in par_p.children if c != p]
# Insert p as a child of q
q.children.append(p)
# If p was root, q is new root
return root
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public:
Node* moveSubTree(Node* root, Node* p, Node* q) {
unordered_map<Node*, Node*> parent;
function<void(Node*, Node*)> dfs = [&](Node* node, Node* par) {
if (!node) return;
parent[node] = par;
for (auto child : node->children)
dfs(child, node);
};
dfs(root, nullptr);
function<bool(Node*, Node*)> is_descendant = [&](Node* node, Node* target) {
if (node == target) return true;
for (auto child : node->children)
if (is_descendant(child, target)) return true;
return false;
};
if (is_descendant(p, q)) {
Node* par_q = parent[q];
if (par_q) {
auto& v = par_q->children;
v.erase(remove(v.begin(), v.end(), q), v.end());
}
Node* par_p = parent[p];
if (par_p) {
auto& v = par_p->children;
v.erase(remove(v.begin(), v.end(), p), v.end());
}
p->children.push_back(q);
return root == q ? p : root;
} else {
Node* par_p = parent[p];
if (par_p) {
auto& v = par_p->children;
v.erase(remove(v.begin(), v.end(), p), v.end());
}
q->children.push_back(p);
return root;
}
}
};
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int val) {
this.val = val;
this.children = new ArrayList<>();
}
public Node(int val, List<Node> children) {
this.val = val;
this.children = children;
}
};
*/
class Solution {
Map<Node, Node> parent = new HashMap<>();
public Node moveSubTree(Node root, Node p, Node q) {
dfs(root, null);
if (isDescendant(p, q)) {
Node parQ = parent.get(q);
if (parQ != null) parQ.children.remove(q);
Node parP = parent.get(p);
if (parP != null) parP.children.remove(p);
p.children.add(q);
return root == q ? p : root;
} else {
Node parP = parent.get(p);
if (parP != null) parP.children.remove(p);
q.children.add(p);
return root;
}
}
private void dfs(Node node, Node par) {
if (node == null) return;
parent.put(node, par);
for (Node child : node.children) {
dfs(child, node);
}
}
private boolean isDescendant(Node node, Node target) {
if (node == target) return true;
for (Node child : node.children)
if (isDescendant(child, target)) return true;
return false;
}
}
/**
* // Definition for a Node.
* function Node(val, children) {
* this.val = val;
* this.children = children || [];
* };
*/
/**
* @param {Node} root
* @param {Node} p
* @param {Node} q
* @return {Node}
*/
var moveSubTree = function(root, p, q) {
const parent = new Map();
function dfs(node, par) {
if (!node) return;
parent.set(node, par);
for (const child of node.children) {
dfs(child, node);
}
}
dfs(root, null);
function isDescendant(node, target) {
if (node === target) return true;
for (const child of node.children) {
if (isDescendant(child, target)) return true;
}
return false;
}
if (isDescendant(p, q)) {
const parQ = parent.get(q);
if (parQ) parQ.children = parQ.children.filter(c => c !== q);
const parP = parent.get(p);
if (parP) parP.children = parP.children.filter(c => c !== p);
p.children.push(q);
return root === q ? p : root;
} else {
const parP = parent.get(p);
if (parP) parP.children = parP.children.filter(c => c !== p);
q.children.push(p);
return root;
}
};
Given the root of an N-ary tree and two nodes p and q in the tree, move the subtree rooted at p to become a direct child of q. If q is already in the subtree rooted at p, you must move q (and its subtree) to become a child of p instead, in order to avoid cycles.
There is always exactly one valid solution per the constraints, and you must not create cycles or duplicate nodes in the tree. The nodes p and q are guaranteed to be different and exist in the tree.
root, p, and q nodes.
At first glance, the problem seems to be a standard tree manipulation task, but the requirement to avoid cycles and the possible case where q is a descendant of p adds a subtle twist.
The brute-force approach would be to traverse the tree to remove p from its current parent and attach it under q. However, if q is in the subtree of p, simply attaching p under q would create a cycle. To avoid this, we must check if q is a descendant of p and, if so, instead move q under p.
Therefore, the key steps are:
p and q.Let's break down the solution into clear steps:
p under q, check if q is a descendant of p. If so, moving p under q would create a cycle, so we need to move q under p instead.
q is a descendant of p:
q from its parent.p from its parent.q as a child of p.q was the root, p becomes the new root.p from its parent.p as a child of q.
We use a hash map for parent lookups (O(1) time per query), and a recursive function to check for descendant relationships. All tree manipulations are performed by modifying the children lists of the respective parent nodes.
Example:
Suppose the tree is:
1
/ | \
2 3 4
|
5
Let p = 4 and q = 5.
{2:1, 3:1, 4:1, 5:4}.
q=5 a descendant of p=4? Yes, since 5 is under 4.
1
/ | \
2 3
|
4
|
5
Now, 4 is a child of 1, and 5 is a child of 4.
This process ensures that the tree remains valid and acyclic.
q is a descendant of pThe key to solving the "Move Sub-Tree of N-Ary Tree" problem is careful bookkeeping of parent-child relationships and handling the special case where the move would create a cycle. By mapping parents and checking for descendant relationships, we can efficiently and safely restructure the tree in O(N) time. The approach is both robust and simple, leveraging standard tree traversal and manipulation techniques.