难度: Hard
Submission
运行时间: 61 ms
内存: 17.0 MB
"""
# 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':
dummy = Node(children = [root])
p_fa,q_fa,is_p_over_q = None,None,False # p是不是q的fa
def dfs(u,fa,is_under_p):
nonlocal p_fa,q_fa,is_p_over_q
if u == p:
p_fa,is_under_p = fa,True
if u == q:
q_fa = fa
is_p_over_q = is_under_p
for v in u.children:
dfs(v,u,is_under_p)
dfs(root,dummy,False)
if p_fa == q:
return root
if is_p_over_q:# p是q的fa
q_fa.children.remove(q)
idx = p_fa.children.index(p)
p_fa.children[idx] = q
else:
p_fa.children.remove(p)
q.children.append(p)
return dummy.children[0]
Explain
此题解的核心思路是通过一次深度优先搜索（DFS）找到节点p和q的父节点以及判断p是否位于q的子树中。首先，创建一个虚拟根节点，其唯一的子节点是真实的根节点，这样可以统一处理边界条件。在DFS过程中，如果遇到节点p，则记录其父节点并标记当前路径下所有节点都在p的子树中。类似地，遇到节点q时记录其父节点。若此时已标记在p的子树中，则表明q在p的子树中。处理移动逻辑时，考虑两种情况：若p直接是q的父节点，则不需要移动；若p在q的子树中，需要先从q的父节点子列表中移除q，再将q作为p的子节点。若p不在q的子树中，则从p的父节点子列表中移除p，并将p作为q的子节点。
时间复杂度: O(n)
空间复杂度: O(n)
# 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':
dummy = Node(children = [root]) # 创建虚拟根节点
p_fa,q_fa,is_p_over_q = None,None,False # 初始化父节点和位置关系
def dfs(u,fa,is_under_p): # 深度优先搜索
nonlocal p_fa,q_fa,is_p_over_q
if u == p: # 找到p
p_fa,is_under_p = fa,True
if u == q: # 找到q
q_fa = fa
is_p_over_q = is_under_p
for v in u.children:
dfs(v,u,is_under_p)
dfs(root,dummy,False) # 从虚拟根开始DFS
if p_fa == q: # p是q的直接父节点
return root
if is_p_over_q: # p是q的fa
q_fa.children.remove(q)
idx = p_fa.children.index(p)
p_fa.children[idx] = q
else:
p_fa.children.remove(p)
q.children.append(p) # 将p移动为q的子节点
return dummy.children[0] # 返回真实的根节点
Explore
在DFS过程中，确保每个节点只被访问一次的关键在于递归的结构。每当进入一个节点时，它会自动递归地访问其所有子节点。由于树结构的特性，没有回路，因此每个节点只会在其父节点被访问时被访问一次，不需要额外的机制来防止重复访问。这种深度优先搜索确保了每个节点只被访问一次，从而避免了性能损失。
创建虚拟根节点主要是为了处理根节点也可能是移动操作的目标或源节点的情况，这样可以避免处理根节点的特殊情况。虚拟根节点作为所有节点（包括原始根节点）的父节点，这样在处理节点的父子关系时，即使是根节点也可以像处理其他节点一样，简化了代码逻辑，避免了在处理根节点时需要额外的条件判断。
在子节点列表很大时，执行`remove`操作效率较低，因为这需要遍历整个子节点列表来找到要删除的节点，其时间复杂度为O(n)。若要提高效率，可以考虑使用哈希集合（HashSet）来存储子节点，这样删除和查找操作的平均时间复杂度都是O(1)。然而，这需要额外的空间来存储哈希值，并可能需要更复杂的节点管理策略来维护父子关系的一致性。
如果p和q是同一个节点，根据题解的逻辑，首先会确定p（即q）的父节点，然后检查是否p在q的子树中，这里会发现p确实在自己的子树中。然后，根据算法逻辑，会尝试将p（作为q）移动到其自身为子节点，这实际是不需要任何操作的。因此，在p和q为同一节点时，本质上不会进行任何移动操作，算法会直接返回原始的根节点。