难度: Medium
Submission
运行时间: 20 ms
内存: 16.7 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
parent, right = None, None
while root:
left = root.left
root.left = right
right = root.right
root.right = parent
parent = root
root = left
return parent
Explain
这个题解采用了迭代的方式来翻转二叉树。通过将每个节点的左右子树进行交换,并同时记录该节点的父节点和原右子树,就可以实现二叉树的上下翻转。具体来说,使用 parent 变量记录当前节点的父节点,right 变量暂存当前节点的右子树,然后将当前节点的左子树赋给 root.left,右子树赋为 parent,最后更新 parent 为当前节点,并将 root 指向原左子节点,进入下一次迭代。当 root 为空时,新的树根就是 parent。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
parent, right = None, None
while root:
left = root.left
root.left = right # 将当前节点的左子树指向原右子树
right = root.right # 暂存当前节点的右子树
root.right = parent # 将当前节点的右子树指向父节点
parent = root # 更新 parent 为当前节点
root = left # 进入下一次迭代,root 指向原左子节点
return parent # 返回新的树根 parent
Explore
在上下翻转二叉树的过程中，我们的目标是将原始的树结构中的每一层节点从左到右的连接关系转变为从上到下的连接关系。这意味着原来的左子节点将成为新的根节点，而原来的根节点将转变为新的右子节点。因此，我们需要从左子节点开始迭代，逐步向下进行，使每个节点的左子节点成为新的根节点。如果同时考虑右子节点，会导致迭代逻辑复杂化，并且与翻转的目标结构不符，因此选择仅通过左子节点向下进行。
在迭代过程中，我们通过使用一个额外的变量 `right` 来暂存当前节点的右子树。每次迭代时，我们首先将 `right` 变量设置为当前节点的右子节点，然后在处理下一个节点之前，我们不再改变 `right` 的值。这样，每个节点的右子树都被安全地保存在 `right` 变量中，直到这个节点被处理完毕，确保了在整个迭代过程中不会丢失对任何右子树的引用。
`parent` 变量在算法中用于保存当前节点的父节点，这是因为在翻转过程中原来的父节点将变成新的右子节点。因此，我们需要一个变量来记录这个信息，以便于将当前节点的右子树指针指向其原父节点。`right` 变量则用于暂存当前节点的原右子树。在迭代过程中，当前节点的左子树会被赋给 `root.left`，而原右子树存储在 `right` 中，将在下次迭代中被重新赋值给新的节点的左子树，从而保持树结构的正确性。
在树的翻转过程结束时，原始树根节点将变成新树的最右下的叶节点。原始树根的左子树将转变为其右子节点，而其右子树将转变为其左子树。这种变化是通过迭代过程中连续更新节点的左右指针来完成的。最终，树的最初始根节点的左右子树将被交换，使其符合翻转后的新结构。