翻转二叉树

难度: Easy

给定一棵二叉树的根节点 root，请左右翻转这棵二叉树，并返回其根节点。

示例 1：

输入：root = [5,7,9,8,3,2,4]
输出：[5,9,7,4,2,3,8]

提示：

树中节点数目范围在 [0, 100] 内
-100 <= Node.val <= 100

注意：本题与主站 226 题相同：https://leetcode-cn.com/problems/invert-binary-tree/

Submission

运行时间: 56 ms

内存: 14.8 MB

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def mirrorTree(self, root: TreeNode) -> TreeNode:
        if root is None:
            return root
        root.left, root.right = self.mirrorTree(root.right), self.mirrorTree(root.left)
        return root

Explain

该题解采用递归的方式进行二叉树的翻转。对于每一个节点，首先递归地翻转其右子树，然后递归地翻转其左子树。完成这两个步骤后，交换当前节点的左右子节点。这个过程会递归地应用到每一个非空节点，直到所有的节点都被访问并翻转其左右子树。

时间复杂度: O(n)

空间复杂度: O(h) where h is the height of the tree, worst case O(n)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def mirrorTree(self, root: TreeNode) -> TreeNode:
        if root is None:
            return root  # 如果节点为空，直接返回
        # 递归地翻转右子树和左子树
        root.left, root.right = self.mirrorTree(root.right), self.mirrorTree(root.left)
        return root  # 返回翻转后的根节点

Explore

在递归翻转二叉树的过程中，首先翻转右子树再翻转左子树的顺序实际上并不会影响最终的结果。无论是先翻转右子树还是左子树，最终的操作是将两者的位置进行交换。因此，这种顺序只是递归实现的一种选择，并没有特定的逻辑或性能上的优势。可以根据个人习惯或者特定需求来调整递归的顺序。

如果二叉树的结构非常不平衡，例如所有节点都只有左子树或右子树，这将导致递归的深度等于树的高度，即递归栈的最大深度也等于树的高度。这种情况下，递归解法的时间和空间复杂度都将受到影响。时间复杂度依然是O(n)，因为每个节点仍然只访问一次。但是，空间复杂度在最坏情况下会达到O(n)，因为递归栈的深度最大可能与节点数相同。这可能导致在极端情况下性能问题或栈溢出。

在递归过程中判断节点是否为空是必须的，因为这是递归终止的条件之一。如果不进行这样的判断，当递归到叶子节点的子节点（即null）时，程序将尝试访问空引用，从而导致错误。此外，这一步骤确保了只有非空节点会被处理和交换，保证了算法的正确性和稳定性。

翻转二叉树的操作会改变树中每个节点的左右子节点的位置，因此原有的二叉树结构被完全覆盖。但是，这个操作是可逆的。如果对翻转后的树再次执行相同的翻转操作，可以恢复到原树的结构。因此，尽管原结构被覆盖，但可以通过相同的翻转操作来恢复。