LCR 144.翻转二叉树
难度：🟢 简单
标签：树、深度优先搜索、二叉树、递归
链接：LCR 144. 翻转二叉树 (LeetCode 226. Invert Binary Tree)
题目描述
给定一棵二叉树的根节点 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 = []
输出：[]
解题思路
核心思想
本题的核心思想是递归地交换树中每一个节点的左、右子节点。要翻转整棵树，我们只需要翻转其根节点的左右子树，然后将这两棵已经翻转过的子树交换位置即可。
思路选择
深度优先搜索（DFS），特别是通过递归实现，是解决此问题最自然、最简洁的方法。我们可以定义一个函数，其功能是接收一个节点，翻转以该节点为根的子树，并返回翻转后的子树的根。此题解推荐在原树上进行修改（原地翻转），以获得最优的空间效率。
关键步骤
递归的终止条件 (Base Case)：如果当前节点
root为null，说明它是一棵空树，无需翻转，直接返回null。递归分解 (后序遍历)： a. 递归调用函数，翻转当前节点的左子树。 b. 递归调用函数，翻转当前节点的右子树。
交换与返回 (处理根节点)： a. 当左右子树都已成功翻转后，交换当前
root节点的left和right指针。 b. 返回当前root节点。
代码实现 (推荐 - 原地翻转)
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var invertTree = function (root) {
// Base Case: 节点为空，直接返回
if (root === null) {
return null;
}
// 递归翻转左右子树
invertTree(root.left);
invertTree(root.right);
// 交换当前节点的左右子节点
const temp = root.left;
root.left = root.right;
root.right = temp;
return root;
};
原始代码分析 (用户提供)
您提供的代码也是一种正确的递归解法，但它通过创建新节点来构建一棵全新的、翻转后的树，而不是在原始树上进行修改。
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var flipTree = function (root) {
// 终止条件
if(root === null) return null;
// 创建一个新节点，其左右子节点是递归翻转后的 right 和 left 子树
// 这种方法不修改原始树，而是返回一个全新的树
return new TreeNode(root.val, flipTree(root.right), flipTree(root.left))
};
优点：采用了函数式编程的思想，不修改原始输入数据（immutable），而是返回一个全新的结果。这在某些场景下可以避免副作用。
待改进：此解法需要为树中的每一个节点都创建一个新的
TreeNode对象，因此空间复杂度较高，为 O(n)。而原地翻转的解法则不需要额外的节点空间。通常情况下，题目期望的是原地翻转的解法以节省空间。
复杂度分析
时间复杂度：O(n) 其中 n 是树的节点总数。每个节点都会被访问一次。
空间复杂度：O(h) 其中 h 是树的高度。空间复杂度主要由递归调用栈的深度决定。
相关题目
总结
本题是二叉树递归操作的入门经典。无论是原地交换还是创建新树，核心都在于递归地处理左右子树，然后对当前节点进行操作。理解前序遍历和后序遍历的不同方式都能解决此问题，可以加深对递归的理解。