LeetCode题练习与总结：翻转二叉树--226

一、题目描述

给你一棵二叉树的根节点 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

二、解题思路

这个问题可以通过递归的方式来解决。递归是一种常用的树结构处理方法，它能够将问题分解为更小的子问题。对于翻转二叉树这个问题，我们可以这样思考：

对于任意一个节点，我们首先翻转它的左右子树。
然后将这个节点的左右子树交换位置。

递归的终止条件是当前节点为空，即到达了叶子节点的子节点，此时不需要做任何操作。

三、具体代码

class Solution {public TreeNode invertTree(TreeNode root) {// 递归终止条件，如果当前节点为空，直接返回if (root == null) {return null;}// 递归翻转当前节点的左右子树TreeNode left = invertTree(root.left);TreeNode right = invertTree(root.right);// 交换当前节点的左右子树root.left = right;root.right = left;// 返回当前节点，此时它的左右子树已经被翻转return root;}
}

这段代码首先检查当前节点是否为空，如果为空则直接返回。如果不为空，则递归调用 invertTree 方法翻转左右子树，然后将左右子树交换。最后返回当前节点，这时当前节点的左右子树已经翻转完成。由于每次递归调用都会交换子树，所以整棵树的所有节点都会被正确翻转。

四、时间复杂度和空间复杂度

1. 时间复杂度

递归方法 invertTree 对于每个节点都会被调用一次，并且每次调用都会访问一次该节点的左右子节点。因此，每个节点都会被访问一次，总的访问次数与节点数成正比。
在二叉树中，每个节点除了根节点外，都有且仅有一个父节点，所以所有节点的入栈和出栈操作总共会被执行2N次（N为树中节点的数量），因此时间复杂度为O(N)，其中N是树中节点的数量。

2. 空间复杂度

递归方法的空间复杂度主要取决于递归调用栈的深度，而递归调用栈的深度在极端情况下（即树完全倾斜时）等于树的高度。
在最坏情况下，树可能是一条链表，其高度为N（N为树中节点的数量），此时递归调用栈的深度也为N，因此空间复杂度为O(N)。
在平均情况下，一棵完全平衡的二叉树的高度大约是log(N)，因此递归调用栈的深度也是log(N)，此时空间复杂度为O(log(N))。

综上所述：

时间复杂度：O(N)，其中N是树中节点的数量。
空间复杂度：最坏情况下为O(N)，平均情况下为O(log(N))。

五、总结知识点

类定义：代码定义了一个名为 Solution 的类，这是Java面向对象编程的基本单位。
方法定义：在 Solution 类中定义了一个名为 invertTree 的公共方法，它接受一个 TreeNode 类型的参数并返回一个 TreeNode 类型的结果。
递归：invertTree 方法使用递归算法来遍历和翻转二叉树。递归是一种自我调用的算法，用于解决能够分解为更小相似问题的问题。
递归终止条件：递归算法通常有一个或多个终止条件，以防止无限递归。在这个方法中，如果当前节点 root 为 null，则直接返回 null，这是递归的终止条件。
引用传递：方法参数 TreeNode root 是通过引用传递的，这意味着在方法内部对 root 的修改会影响到原始的树结构。
二叉树操作：代码涉及了二叉树的基本操作，包括访问节点的左右子节点以及修改节点的左右子节点。
节点交换：通过简单的赋值操作，实现了节点左右子树的交换，这是翻转二叉树的核心步骤。
返回值：在递归的每一步中，都会返回当前节点，以便在递归回溯时保持树结构的完整性。
递归调用栈：虽然代码中没有直接体现，但在递归过程中会隐式地使用调用栈来保存每次递归调用的状态。
类型声明：代码中使用了 TreeNode 类型，这是一个自定义的数据结构，表示二叉树的节点，包含整数值 val 以及指向左右子节点的引用 left 和 right。