0226.翻转二叉树

难度：🟢 简单

标签：树、深度优先搜索、广度优先搜索、二叉树、递归

链接：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 = []
输出：[]

解题思路

核心思想

本题的核心思想是递归地交换树中每一个节点的左、右子节点。要翻转整棵树，我们只需要翻转其根节点的左右子树，然后将这两棵已经翻转过的子树交换位置即可。

思路选择

深度优先搜索（DFS），特别是通过递归实现，是解决此问题最自然、最简洁的方法。我们可以定义一个函数，其功能是接收一个节点，翻转以该节点为根的子树，并返回翻转后的子树的根。

关键步骤

1. 递归的终止条件 (Base Case)：如果当前节点 root 为 null，说明它是一棵空树，无需翻转，直接返回 null。

2. 递归分解 (后序遍历)： a. 递归调用函数，翻转当前节点的左子树。 b. 递归调用函数，翻转当前节点的右子树。

3. 交换与返回 (处理根节点)： 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 invertTree = function (root) {
    // 终止条件
    if (root === null) return root;
    // 递归翻转左右子树，得到翻转后的子树
    let leftTree = invertTree(root.left);
    let rightTree = invertTree(root.right);

    // 创建一个新节点，其左右子节点是翻转后的 rightTree 和 leftTree
    return new TreeNode(root.val, rightTree, leftTree);
};

• 优点：采用了函数式编程的思想，不修改原始输入数据，而是返回一个全新的结果。这在某些场景下可以避免副作用。

• 待改进：此解法需要为树中的每一个节点都创建一个新的 TreeNode 对象，因此空间复杂度较高，为 O(n)。而原地翻转的解法则不需要额外的节点空间。通常情况下，题目期望的是原地翻转的解法。

复杂度分析

• 时间复杂度：O(n) 其中 n 是树的节点总数。每个节点都会被访问一次。

• 空间复杂度：O(h) 其中 h 是树的高度。空间复杂度主要由递归调用栈的深度决定。

相关题目

• 0101.对称二叉树

• 0100.相同的树

总结

本题是二叉树递归操作的入门经典。无论是原地交换还是创建新树，核心都在于递归地处理左右子树，然后对当前节点进行操作。理解前序遍历和后序遍历的不同方式都能解决此问题，可以加深对递归的理解。