翻转二叉树全解：从递归到迭代，吃透力扣热题100经典题-嵌云网-嵌入式AI开发资源站

翻转二叉树全解：从递归到迭代，吃透力扣热题100经典题

抹茶柚子冰·2026-09-09·阅读 21 GEO检测（免费）

翻转二叉树二叉树递归

|难度：普通|阅读约 30 分钟

刷过力扣的朋友对这道题肯定不陌生——翻转二叉树，力扣热门100题里典型的“看起来简单、写起来翻车率极高”的代表。尤其是当年Homebrew的作者Max Howell面试谷歌因为没写出反转二叉树被拒的段子传开后，这道题几乎成了算法面试圈的“梗王”。但它能进热题100，靠的可不是段子，而是背后覆盖的递归思维、遍历框架、复杂度分析以及边界处理能力，都是面试高频考点。

这篇文章我从题目拆解、递归写法、迭代写法、边界分析、变体扩展到刷题顺序建议，一次性讲透。不管你是刚开始刷力扣的新手，还是准备冲刺大厂面试、想系统过一遍热题100的同学，这篇都能给你一些可复用的思路和实操经验。

1. 题目到底在考什么——先别急着写代码

1.1 题目描述与示例

先看题面。给你一棵二叉树的根节点 root，翻转这棵二叉树，并返回其根节点。什么叫翻转？简单说，就是把这棵树的每一个节点的左右子树都交换。

举个例子，输入：

code复制     4
   /   \
  2     7
 / \   / \
1   3 6   9

翻转后输出：

code复制     4
   /   \
  7     2
 / \   / \
9   6 3   1

注意看，不只是根节点的左右孩子交换，而是每一个节点的左右子树都交换。这也是很多人第一次写的时候容易踩的坑——只换了根节点的左右孩子，下面的节点全没动，结果只翻转了一层。

1.2 核心考点分析

这道题虽然叫“翻转二叉树”，但本质上考察的是三件事：

第一，对二叉树结构的理解是否到位。 二叉树的每个节点都有左指针和右指针，翻转操作就是交换这两个指针。但二叉树是递归定义的——每个子树本身也是一棵二叉树，所以只处理当前节点远远不够，必须“下沉”到每一个子树去做同样的操作。

第二，对递归框架的掌握程度。 二叉树的题80%都能用递归解决，翻转二叉树就是最典型的递归入门题之一。很多人在这一步暴露了问题：递归终止条件写不好，或者递归调用顺序搞错，导致结果不对甚至栈溢出。

第三，是否具备“一题多解”的意识。 递归解法最简洁，但面试官往往追问一句“能不能用迭代实现”。这考察的是你对栈、队列这些基础数据结构的掌握，以及对深度优先遍历（DFS）和广度优先遍历（BFS）的理解是否扎实。

1.3 为什么递归是这道题的天然解法

二叉树本身就是递归定义的——每个节点的左右孩子仍然是二叉树。因此，当你对一棵二叉树做某种操作时，很自然的思路就是：先处理当前节点，再递归处理左右子树。

翻转一棵树的过程可以拆解为：

当前节点的左右子树交换；
递归翻转左子树；
递归翻转右子树。

这里有个好消息：这两步的先后顺序其实不影响最终结果。你先递归翻转子树再交换，或者先交换再递归翻转子树，结果都一样，因为交换操作和递归操作发生在不同的结构层级上。但有一个前提——你不能在一棵子树上重复操作两次，这就引出了后面要讲的中序遍历陷阱。

需要模型API调用？免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。

2. 递归解法：最简洁也最需要想清楚的写法

2.1 递归三步法：终止条件、单层逻辑、返回值

写递归算法，我习惯先想清楚三件事，这也是面试时展示思路的好方式：

终止条件：什么时候不需要再递归了？当节点为 None 时，没有可翻转的内容，直接返回 None。

单层逻辑：当前节点要做什么？交换左右子树。

返回值：返回什么？返回翻转后的根节点。因为翻转操作是“原地”的，返回的仍然是当前节点。

把这三件事想清楚，代码几乎是顺水推舟。

2.2 Python实现与核心代码剖析

直接看代码：

python复制def invert_tree(root):
    if not root:
        return None
    
    # 交换当前节点的左右子树
    root.left, root.right = root.right, root.left
    
    # 递归翻转左右子树
    invert_tree(root.left)
    invert_tree(root.right)
    
    return root

这段代码的关键在于：递归调用把翻转操作传播到整棵树的每一个节点。你不需要手动遍历所有节点，递归帮你完成了全部工作。

但这里有个细节很多人会忽略——Python里 root.left, root.right = root.right, root.left 这个交换语句是一步完成的。它的执行顺序是：先把右侧的值都取出来，再依次赋值给左侧。所以这里不存在“先交换了左子树，导致右子树引用丢失”的问题。

如果你拆开写成两句：

python复制root.left = root.right
root.right = root.left

那就出大问题了——左子树被覆盖，右子树指向了原来的左子树，树的结构直接坏掉。这种低级错误在面试高压环境下并不少见，建议你记住这一点。

2.3 左右子树交换顺序的讲究

递归版本还有一个容易踩的坑：中序遍历时不能直接交换。

先序遍历的写法是：

python复制def invert_tree(root):
    if not root:
        return None
    root.left, root.right = root.right, root.left
    invert_tree(root.left)
    invert_tree(root.right)
    return root

后序遍历的写法是：

python复制def invert_tree(root):
    if not root:
        return None
    invert_tree(root.left)
    invert_tree(root.right)
    root.left, root.right = root.right, root.left
    return root

两种都对。但如果你写成中序遍历的样子：

python复制def invert_tree(root):
    if not root:
        return None
    invert_tree(root.left)   # 递归处理左子树
    root.left, root.right = root.right, root.left  # 交换
    invert_tree(root.right)  # 递归处理“新的左子树”
    return root

看起来似乎合理，但注意最后一步：交换完之后，原来的右子树变成了左子树，原来的左子树变成了右子树。你继续递归的 root.right 实际上是原来已经处理过的左子树，相当于有一棵子树被处理了两次，另一棵子树完全没被处理。

所以这道题用中序遍历思路做，必须额外记录一个变量保存原来的右子树：

python复制def invert_tree(root):
    if not root:
        return None
    invert_tree(root.left)
    left = root.left
    root.left = root.right
    root.right = left
    invert_tree(root.right)
    return root

这种写法容易出错，面试时不推荐主动展示，除非面试官追问“中序行不行”。提前能说出这个坑，反而能体现你对递归过程的深入理解。

提示：递归解法的核心心法就一句话——相信你的递归函数，它一定能正确翻转你给它的子树。写递归的时候不要在脑子里一层层展开调用栈，否则很容易把自己绕晕。

3. 迭代解法：面试官最爱追问的第二种方案

你写出递归版本之后，面试官大概率会追问：“如果递归深度很大，或者我不想用递归，怎么写？”不要慌，迭代版本其实思路一样，只是把系统维护的调用栈，换成了你自己维护的一个栈或队列。

3.1 用栈模拟DFS：手动维护调用栈

本质上是模拟先序遍历的过程。用一个栈来存放待处理的节点，每次弹出一个节点，交换它的左右孩子，然后把左右孩子压入栈中。

python复制def invert_tree(root):
    if not root:
        return None
    
    stack = [root]
    while stack:
        node = stack.pop()
        node.left, node.right = node.right, node.left
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    
    return root

这个写法其实就是递归版的“翻译”，只是把递归调用换成了显式的栈操作。核心逻辑没变——每个节点都弹出、交换、压入子节点，直到栈空，遍历完所有节点。

注意一个细节：先压左还是先压右都没有关系，因为每个节点都会独立处理，最终结果完全一样。这一点和遍历顺序相关的题目（比如前序输出）不同，翻转二叉树不要求输出顺序，只要求结构变化。

3.2 层序遍历队列法：BFS解法写起来更顺

除了栈模拟深度优先遍历，用队列做广度优先遍历也很直观。从根节点开始，逐层处理，每一层都交换当前节点的左右孩子，然后把孩子节点入队。

python复制from collections import deque

def invert_tree(root):
    if not root:
        return None
    
    queue = deque([root])
    while queue:
        node = queue.popleft()
        node.left, node.right = node.right, node.left
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    
    return root

我个人觉得，BFS版本的代码语义最好理解——它天然符合“一层层翻过去”的直觉。你从根节点出发，处理一层再处理下一层，逻辑清晰，也不容易出错。

3.3 递归、栈迭代、队列迭代，到底该用哪种

三种解法都能通过，时间复杂度和空间复杂度也几乎一样，区别主要在代码风格和应用场景上。我帮你梳理了一下：

解法	核心数据结构	遍历方式	代码量	适用场景
递归	系统调用栈	DFS	最少	默认首选，简单直观
栈迭代	显式栈	DFS	中等	面试追问“不用递归怎么写”时
队列迭代	队列	BFS	中等	面试追问“能否层序处理”时

从我的经验看，递归版本是最稳的，面试时优先写递归，然后再补充迭代。因为递归代码短、逻辑清楚、不容易出bug。但前提是你真的理解了递归过程，而不是只背代码。

我在实际面试中常用的话术是：“这道题我可以用递归在O(n)时间内完成，但如果树很深担心栈溢出，我也可以改成用显式栈或队列做迭代实现，思路是一样的，只是把系统栈换成自己的数据结构。”这段话一说出来，面试官对你的印象分就会不一样。

4. 复杂度分析与边界情况——高手和新手的分水岭

代码写出来、能跑通测试，只是第一步。真正拉开差距的，是你能不能把复杂度分析讲清楚，以及边界情况是否想全了。

4.1 时间复杂度和空间复杂度

时间复杂度：O(n)，其中 n 是二叉树节点数。因为每个节点恰好被访问一次，交换操作的时间是 O(1)，所以总时间是 O(n)。不存在平均情况、最坏情况的区别，就是稳定地遍历全部节点。

空间复杂度：O(h)，其中 h 是二叉树的高度。

递归版本的空间复杂度取决于递归调用的深度，也就是树的高度。最坏情况下，树退化成链状结构——每个节点只有一个孩子，此时高度为 n，递归栈深度也是 n，空间复杂度退化为 O(n)。最好情况下，树是平衡的，高度为 O(log n)，空间复杂度就是 O(log n)。

迭代版本的空间复杂度同样依赖于数据结构的存储量。栈或队列中最多可能存储一整层的节点，在完全二叉树的情况下，最后一层节点数约 n/2，所以也是 O(n)。不过如果树退化成链状结构，栈里最多存 1 个节点，空间反而更优。

很多人在面试时只说“O(n)空间复杂度”，没有区分“树高”和“节点数”的关系，这其实是一个可以补充加分的地方。

4.2 常见边界情况自查清单

边界条件处理是否到位，是面试官考察代码质量的重要维度。我总结了一个自查清单，写完后逐个确认：

空树：root 为 None，直接返回 None。递归版本和迭代版本都要求第一步判空。
只有根节点：没有左右孩子，交换后还是自己，结果不变。
只有左子树或只有右子树：交换后，空的那边变成非空，非空那边变成空。比如一个只有左孩子的节点，翻转后变成只有右孩子。这个场景最容易测出“只交换指针”但没有递归处理子节点的问题。
完全二叉树：每一层都满的，处理逻辑一样。
链状树：每个节点只有一个孩子，递归深度等于节点数，容易栈溢出，迭代版本更稳。
多层嵌套：测试用例里经常有 5 层以上的树，翻转结果需要仔细核对每一层。

我自己的习惯是，写完代码后先用 None 测一次，再构一个简单的三节点树测一次，最后跑力扣自带的测试用例。这花不了几秒钟，但能避免不少低级失误。

4.3 一个隐蔽的坑：原地修改与返回节点

这道题要求“原地翻转”，即直接在原树上修改，返回根节点。很多人会被“返回根节点”误导，以为要新建一棵树返回。其实不用，而且新建一棵树的做法既浪费空间，也容易写错。

但原地修改有个隐患：你在修改树结构的同时，如果还有别的变量引用着这棵树的旧结构，那这些引用会“看到”翻转后的结果。如果你后续还要基于翻转前的树做操作，记得先拷贝一份，或者在逻辑上做好拆分。

在面试中，明确说出“这道题是原地操作，不需要返回新树”这句话，也能体现你对题意理解到位。

5. 变体与扩展——一道题吃透一类二叉树问题

翻转二叉树在力扣热题100里不算难，但它和不少题目有关联。如果你能从一个题目延伸出一类题目的解法，面试时会显得思路特别开阔。

5.1 变体一：对称二叉树（力扣101）

判断一棵二叉树是否关于根节点镜像对称。注意，这里的“镜像对称”看起来和“翻转”有点像，但完全是两回事——翻转是把整棵树左右互换，对称判断是比较左子树和右子树是否互为镜像。

判断对称树的递归逻辑是：左节点的左孩子和右节点的右孩子是否相等，左节点的右孩子和右节点的左孩子是否相等。这本质上用了“镜像位置配对”的思想，和翻转二叉树正好是一对“正反题”。

如果你先理解了翻转二叉树，再去写对称二叉树，会发现一个有意思的联系：把一棵树的左子树翻转后，再和右子树比较，如果相等，那这棵树就是对称的。当然，这不一定是解题的最优思路，但对加深二叉树递归的理解很有帮助。

5.2 变体二：二叉树展开为链表（力扣114）

这道题要求把二叉树“展开”成一个单链表，展开顺序符合先序遍历顺序，每个节点的右指针指向下一个节点，左指针置空。

展开的核心思路也是递归：先把左子树展开成链表，再把右子树展开成链表，然后把左子树的链表接到当前节点的右指针上，最后把原来的右子树接到左子树链表的末尾。

这个题比翻转二叉树多了一个“重接指针”的操作，但从思维模型上来讲，它们是一脉相承的——都是通过递归把问题分解为“处理当前节点 + 处理左右子树”。

5.3 面试官追问套路与应对策略

在面试场景里，翻转二叉树还可能被这么问：

追问1：“你刚才用了递归，能说说递归在这里的空间复杂度吗？如果树很深会怎样？”

这题考察的就是你能否说清递归栈和树高的关系，以及你是否有迭代方案的备选。

追问2：“如果这棵树特别大，内存放不下怎么办？”

这就是开放题了，考察大数据处理思维。常见的展开方向包括：外部存储 + 逐块读入处理、分布式并行处理——每台机器处理一棵子树再合并结果。当然，这些方案在面试中点到为止即可，不需要真的把代码写出来。

追问3：“能不能用层序遍历实现？和递归的差别是什么？”

考察你的BFS功底，以及是否理解 DFS 和 BFS 的适用场景差异。翻转二叉树没有遍历顺序的硬性要求，因此DFS和BFS都能做，这也是为什么这道题适合拿来考察“一题多解”。

刷题建议：不要只满足于写出一种解法。把递归、栈迭代、队列迭代三种版本都写一遍，你的收获会比刷三遍这道题还大。这道题我已经刷过很多次了，每次重新写都能发现一些新的理解角度，确实是个常写常新的题目。

6. 实战验证与力扣刷题方法论

6.1 本地如何快速验证代码正确性

力扣自带的测试用例够用，但如果你想在本地调试，自己构建测试用例也很简单。我用 Python 写了一个快速验证的模板，你们可以直接拿来用：

python复制class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def build_tree_from_list(data):
    """根据层序列表构建二叉树，None 表示空节点"""
    if not data:
        return None
    root = TreeNode(data[0])
    queue = [root]
    idx = 1
    while idx < len(data):
        node = queue.pop(0)
        if data[idx] is not None:
            node.left = TreeNode(data[idx])
            queue.append(node.left)
        idx += 1
        if idx < len(data) and data[idx] is not None:
            node.right = TreeNode(data[idx])
            queue.append(node.right)
        idx += 1
    return root


def print_tree(root):
    """层序打印二叉树"""
    if not root:
        print("[]")
        return
    result = []
    queue = [root]
    while queue:
        node = queue.pop(0)
        if node:
            result.append(node.val)
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append(None)
    while result and result[-1] is None:
        result.pop()
    print(result)


# 测试
root = build_tree_from_list([4, 2, 7, 1, 3, 6, 9])
print("原始树：")
print_tree(root)

inverted = invert_tree(root)
print("翻转后：")
print_tree(inverted)

这个模板的好处是你可以在本地随意构造各种形状的树，包括空树、单节点树、链状树等边界情况，把代码跑熟之后再去力扣提交，心里特别踏实。

6.2 这道题在力扣热题100里的定位与作用

力扣热题100是很多人秋招、春招刷题的主线，翻转二叉树在其中的定位很有意思——它不属于难题，但却是检验“二叉树递归基础”是否扎实的试金石。

如果你刚开始刷二叉树，我建议按照这个顺序走：

基础遍历类：前序、中序、后序、层序遍历——先把四种遍历吃透；
结构操作类：翻转二叉树、合并二叉树、对称二叉树——理解递归如何操作树结构；
路径与深度类：二叉树的最大深度、最小深度、路径总和——把递归和回溯结合；
构造与转换类：从前序与中序构造二叉树、二叉树展开为链表——综合能力；
高级应用类：最近公共祖先、二叉搜索树转累加树——题目越来越综合。

翻转二叉树处在第2步，它的作用就是让你熟练“递归处理整棵树”的感觉。这个手感一旦建立起来，后面的最大深度、平衡二叉树、路径总和这些题，写起来会顺手很多。

6.3 进大厂面试，刷力扣到底在测什么

很多同学问“进大厂为什么要刷力扣”，我心里很理解这个疑问。说实话，翻过多年的面试经验，面试官让你写翻转二叉树，真不是期望你背下这道题的答案。他们考察的是这几项底层能力：

代码能否快速落地。给你10分钟，你能不能从零开始定义数据结构、写出正确的递归、跑通测试？这反映的是工程编码基本功。

边界意识。空树怎么办？只有一个节点怎么办？链状树会不会递归太深？这些细节直接暴露你平时写代码的习惯。

沟通与推导能力。写之前清不清楚讲解思路？卡住的时候会不会主动交流？被追问时能不能快速给出备选方案？这才是热题100真正训练的东西。

所以刷题不是目的，通过刷题把“想清楚再动手、写代码时考虑边界、遇到问题能换思路”变成肌肉记忆，才是刷力扣的真正价值。

7. 一些杂七杂八的经验

刷了这么多题，关于翻转二叉树这道题，我有几个亲测有效的体会想分享。

第一，别死记代码。 很多同学看了题解，把递归版背下来就觉得自己会了。结果面试官一追问“换种方式写”，当场卡壳。我的建议是：先读懂思路，关上答案自己写一遍，再换成栈迭代写一遍，BFS写一遍。同一个题写三遍，比刷三个不同的题有用得多。

第二，面试时不要急着写代码，先讲思路。 哪怕是翻转二叉树这种经典题，你也先说一句“这道题可以用递归，每个节点交换左右子树，然后递归处理左右子节点”。这既是给自己理清思路，也是给面试官一个信号——你写代码前有思考过程。

第三，递归代码尽量保持简洁。 我见过有些同学为了“避免递归栈溢出”，写一个非常复杂的迭代版本，结果代码又长又容易出bug。算法题要的就是“清晰正确地解决问题”，先能用最简洁的方式做对，再谈优化。如果面试官担心栈溢出，你提一嘴“也可以写成迭代版”就够了，他真要你写，你再写不迟。

第四，力扣的题目描述里有很多隐含信息。 比如这道题的示例里，输入输出是层序遍历的表示形式，但实际操作的是树结构，不是数组。很多人一开始没搞清楚这点，直接拿数组做交换，结果肯定不对。先读懂题，再动手，永远是第一原则。

翻转二叉树这道题，代码量不大，但能把递归、迭代、复杂度分析、边界情况、面试沟通整个流程完整走一遍。如果你正在刷热题100，建议认真把这题吃透，不要跳过去。它不只是一道“看了答案就会”的简单题，更是一块检验你二叉树基本功的试金石。