[翻转二叉树](https://leetcode.cn/problems/invert-binary-tree/description/) ## 题目描述 给你一棵二叉树的根节点 root，翻转这棵二叉树，并返回其根节点。 翻转的含义：交换每个节点的左右子树。 **示例** ```text 输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1] 4 4 / \ / \ 2 7 → 7 2 / \ / \ / \ / \ 1 3 6 9 9 6 3 1 ``` ```text 输入：root = [2,1,3] 输出：[2,3,1] 2 2 / \ → / \ 1 3 3 1 ``` ```text 输入：root = [] 输出：[] ``` ## 解题思路 对于二叉树的题目，解决思路基本就是二叉树的遍历模版，二叉树天然就是递归形成的，解题也是寻找递归(子问题)的过程。 **二叉树的定义** ```text 二叉树是 n（n ≥ 0） 个节点的有限集合，它满足： - 当 n = 0 时，称为空二叉树 - 当 n > 0 时，有且仅有一个节点称为根节点（Root） - 其余节点被分成两个互不相交的子集： 左子树（Left Subtree） 和 右子树（Right Subtree）， 且这两个子集本身也都是二叉树 ``` **切入点** ```text 翻转二叉树 - 从根节点出发 将根节点的左右节点(记作A,B) 变化根节点的左右指向 此时变为B,A - 继续出发 B 和 A 上的每个节点 也执行相同的操作 - 此时 就实现了 翻转二叉树 ------ 总结 根节点左右节点翻转 并且左子树和右子树上每个节点翻转 ``` **解题代码** ```python # 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: Optional[TreeNode]) -> Optional[TreeNode]: if not root: return None left = self.invertTree( root.left ) right = self.invertTree( root.right ) root.left = right root.right = left return root ``` **时间复杂度: `O(n)`** **空间复杂度: `O(h)`** n = 节点总数 h = 树的高度 ( 最坏情况`O(n)` 最好情况`O(log n)` )