翻转二叉树 - Stellar Observer Protocol

544 字

3 分钟

翻转二叉树

2025-08-14

Algorithms

树

/

深度优先搜索

/

广度优先搜索

/

二叉树

题目描述#

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

解题思路#

递归分治法：
- 采用二叉树的后序遍历（左→右→根）
- 递归翻转左子树
- 递归翻转右子树
- 交换当前节点的左右子树
迭代遍历法：
- 使用队列进行层序遍历（BFS）
- 每访问一个节点，立即交换其左右子树
- 将子节点加入队列继续处理
前序替代方案：
- 前序遍历（根→左→右）同样可行
- 先交换子树再递归处理

关键洞察#

子树独立性：
- 翻转操作具有递归特性
- 翻转整树 = 翻转左子树 + 翻转右子树 + 交换左右子树
交换本质：
- 只需交换左右子节点指针
- 无需修改节点值或创建新节点
遍历顺序无关性：
- 先序/后序/层序遍历均可完成翻转
- 中序遍历需调整（避免重复处理）
原地修改特性：
- 所有操作在原始树上进行
- 空间复杂度仅依赖于遍历方式

复杂度分析#

方法	时间复杂度	空间复杂度
递归法	O(n)	O(h) [树高, 最坏O(n)]
迭代BFS	O(n)	O(w) [最大宽度]
迭代DFS	O(n)	O(h) [树高]

注：n 为节点总数，h 为树高度，w 为树最大宽度

代码实现#

递归法

1
/**
2
 * Definition for a binary tree node.
3
 * function TreeNode(val, left, right) {
4
 *     this.val = (val===undefined ? 0 : val)
5
 *     this.left = (left===undefined ? null : left)
6
 *     this.right = (right===undefined ? null : right)
7
 * }
8
 */
9
/**
10
 * @param {TreeNode} root
11
 * @return {TreeNode}
12
 */
13
var invertTree = function (root) {
14
    if (!root) return root;
15
    const left = invertTree(root.left);
16
    const right = invertTree(root.right);
17
    root.left = right;
18
    root.right = left;
19
    return root;
20
};

迭代 BFS

1
/**
2
 * Definition for a binary tree node.
3
 * function TreeNode(val, left, right) {
4
 *     this.val = (val===undefined ? 0 : val)
5
 *     this.left = (left===undefined ? null : left)
6
 *     this.right = (right===undefined ? null : right)
7
 * }
8
 */
9
/**
10
 * @param {TreeNode} root
11
 * @return {TreeNode}
12
 */
13
const invertTree = (root) => {
14
    if (!root) return null;
15

16
    const queue = [root];
17
    while (queue.length) {
18
        const node = queue.shift();
19

20
        // 交换当前节点的左右子树
21
        [node.left, node.right] = [node.right, node.left];
22

23
        // 子节点入队
24
        if (node.left) queue.push(node.left);
25
        if (node.right) queue.push(node.right);
26
    }
27
    return root;
28
};