难度: Medium
Submission
运行时间: 31 ms
内存: 16.4 MB
"""
# Definition for a Node.
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.parent = None
"""
class Solution:
def flipBinaryTree(self, root: 'Node', leaf: 'Node') -> 'Node':
arr = []
p = leaf
while p != root:
arr.append(p)
p = p.parent
arr.append(root)
for i in range(len(arr)-1):
p = arr[i]
p0 = arr[i+1]
if p0.left == p:
p0.left = None
else:
p0.right = None
if p.left:
p.right = p.left
p.left = p0
p0.parent = p
# print(p, p.val, p0, p0.val)
# print(p.left, p.right, p.parent)
leaf.parent = None # 调试后才发现漏了这句话
return leaf
Explain
此题解的主要思路在于将二叉树中从给定的叶节点开始到根节点的路径上的所有节点进行翻转。具体步骤如下：首先遍历从叶节点到根节点的路径，将这些节点存储在数组中。然后从叶节点开始，逐个将每个节点的父节点变为它的子节点，同时清除原有的父子关系，并调整兄弟节点的关系。这样，最初的叶节点变成了新的根节点，原来的根节点变成了新根的一个子节点，整个树的结构被反转了。
时间复杂度: O(h)
空间复杂度: O(h)
"""
# Definition for a Node.
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.parent = None
"""
class Solution:
def flipBinaryTree(self, root: 'Node', leaf: 'Node') -> 'Node':
arr = [] # 用来存储从叶节点到根节点的路径
p = leaf # 从叶节点开始
while p != root: # 遍历到根节点
arr.append(p)
p = p.parent
arr.append(root) # 包括根节点在内的完整路径
for i in range(len(arr)-1):
p = arr[i] # 当前节点
p0 = arr[i+1] # 父节点
# 清除原父节点对当前节点的引用
if p0.left == p:
p0.left = None
else:
p0.right = None
# 将原父节点设置为当前节点的左子节点
if p.left:
p.right = p.left
p.left = p0
p0.parent = p # 更新父节点的引用
# print(p, p.val, p0, p0.val)
# print(p.left, p.right, p.parent)
leaf.parent = None # 设置新根节点的父节点为None
return leaf
Explore
为了确保提供的节点`leaf`是一个叶节点，我们可以在代码中添加一个检查步骤来验证此条件。具体来说，可以在`flipBinaryTree`函数的开始处添加如下的检查：`if leaf.left is not None or leaf.right is not None: raise ValueError('提供的节点不是叶节点')`。这种检查可以确保节点没有子节点，从而符合叶节点的定义。
在这个题解中，选择将原父节点放置在当前节点的左侧，主要是为了保持一致的转换规则，即始终将原父节点变为新的左子节点。这样做简化了逻辑，减少了条件判断。将原有的左子节点移至右侧，是为了确保不丢失任何子树。这种方法确保了树的结构在翻转过程中仍然被保持完整。
在这个特定的问题中，树的平衡性不是首要考虑的问题，因为目的是要反转路径，而不是维持树的平衡。然而，在实际的应用中，如果需要维护树的平衡，可能需要在翻转操作后使用树的平衡技术如AVL树或红黑树的旋转操作来重新平衡树。在当前的算法实现中，并未包含处理不平衡的逻辑。
在代码中，根节点的特殊情况通过循环条件`while p != root:`来处理。这个循环会一直执行，直到变量`p`（表示当前正在处理的节点）达到根节点。一旦到达根节点，循环自然结束，因为根节点的父节点是`None`，这也是为什么在循环之后还需要将`root`添加到路径数组`arr`中的原因。这样确保了即使根节点没有父节点，整个翻转操作也能正确完成。