难度: Easy
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：
输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1]
示例 2：
输入：root = [2,1,3] 输出：[2,3,1]
示例 3：
输入：root = [] 输出：[]
提示：
- 树中节点数目范围在
[0, 100]内 -100 <= Node.val <= 100
Submission
运行时间: 44 ms
内存: 14.9 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 invertTree(self, root: TreeNode) -> TreeNode:
def dfs(root):
if root is None:
return
root.left, root.right = root.right, root.left
dfs(root.left)
dfs(root.right)
dfs(root)
return root
Explain
该题解使用深度优先搜索（DFS）的方式遍历二叉树的每个节点。对于每个遍历到的节点，交换其左右子树，然后递归地对其左右子树分别执行相同的翻转操作。通过这种方式，可以实现对整棵二叉树的翻转。
时间复杂度: O(n)
空间复杂度: O(n)
# 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 invertTree(self, root: TreeNode) -> TreeNode:
def dfs(root):
if root is None:
return
# 交换当前节点的左右子树
root.left, root.right = root.right, root.left
# 递归地翻转左子树
dfs(root.left)
# 递归地翻转右子树
dfs(root.right)
dfs(root)
return root
Explore
在递归函数中首先进行节点的左右子树交换，然后递归地翻转子树是为了确保每个节点的子树都被正确地交换。如果先递归子树再进行交换，那么在交换当前节点的左右子树之前，其子树已被翻转，这样会导致双重翻转，即子树被错误地还原到原始状态。因此，先交换后递归是为了保证每个节点及其子节点都按照正确的顺序进行翻转，这样可以确保整棵树被正确地翻转。
对空节点直接返回的处理方式确实意味着对空树不进行任何操作，这是最优的处理策略。因为空树没有任何节点可供翻转，对其进行操作不仅没有意义，而且可能导致不必要的错误或性能损耗。因此，在递归函数中对空节点进行检查并直接返回，是防止对空树进行无效操作的一种有效方式。
即使在某个节点的左右子树已经是对称的，也需要继续执行翻转操作。这是因为翻转二叉树的目标是将所有节点的左右子树位置互换，而不仅仅是调整非对称的部分。即使子树对称，翻转操作仍然需要执行以满足整体翻转的要求。虽然这可能看似增加了额外的计算，但在算法的总体复杂度中，这种检查和条件分支可能反而会增加复杂度而非减少，因此直接翻转是更为直接和高效的策略。