翻转二叉树 | 流年石刻

好的，我们来彻底讲明白如何在 JavaScript 中翻转一棵二叉树。

这不仅仅是一个经典的算法问题，它还因为一则著名的轶事而广为人知：流行的软件包管理器 Homebrew 的作者 Max Howell 在 Google 面试时因为没能现场写出这个算法而被拒。这足以说明，理解它背后的原理非常重要。

我们将从问题本身出发，通过第一性原理推导出解决方案，然后提供并解析两种主流的实现方法：递归和迭代。

1. 核心问题：什么是“翻转”二叉树？

首先，我们需要一个二叉树的节点结构。在 JavaScript 中，通常用一个对象来表示：

JavaScript

// 二叉树节点的构造函数
function TreeNode(val, left, right) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
}

“翻转”或者叫“镜像”一棵二叉树，意味着对于树中的每一个节点，它的左子树和右子树都要互相交换位置。

让我们看一个具体的例子：

原始二叉树:

翻转后的二叉树:

观察上图，你会发现：

根节点 4 的左孩子 2 和右孩子 7 交换了位置。
对于新的左孩子 7，它原来的左孩子 6 和右孩子 9 也交换了位置。
对于新的右孩子 2，它原来的左孩子 1 和右孩子 3 也交换了位置。
这个交换操作一直持续到树的末端。

2. 从根本上思考：如何实现这个交换？

这个问题的核心是“对每一个节点都执行相同的操作”。这种描述天然地指向了两种策略：递归 (Recursion) 和 迭代 (Iteration)。

逻辑推演（递归思路）

最简化问题：如果这棵树只有一个节点（根节点），或者干脆是空的（null），需要翻转吗？不需要。这自然成为了我们思考的基线条件 (Base Case)。如果一个节点是 null，我们直接返回即可，因为没有东西可以翻转。
扩展一步：假设我们有一个节点，它有左、右两个孩子（但这两个孩子没有后代）。我们要翻转这棵树，需要做什么？很简单，只需要交换它的左右孩子。

JavaScript
```
// 伪代码
let temp = node.left;
node.left = node.right;
node.right = temp;
```
推广到整个树：现在我们来看一个完整的树。对于根节点，我们执行了第2步的交换操作。但这就够了吗？显然不够。我们交换过来的新的左子树（原来是右子树）本身也需要被翻转。同理，新的右子树（原来是左子树）也需要被翻转。

这就形成了一个完美的递归结构：
- 定义一个函数 invertTree(node)：它的功能是翻转以 node 为根的这棵子树。
- 函数体：
  1. 处理基线条件：如果 node 是 null，直接返回。
  2. 交换 node.left 和 node.right。
  3. 对新的左子树（也就是原来的右子树）递归调用 invertTree。
  4. 对新的右子树（也就是原来的左子树）递归调用 invertTree。

这个逻辑是自洽且完备的。它保证了从上到下，每一层的每一个节点都会被正确处理。

3. JavaScript 实现与解析

方法一：递归解法 (DFS - 深度优先搜索)

递归的实现方式直接翻译了我们上面的逻辑推演，代码非常简洁、优雅。

JavaScript

/**
 * 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) {
    // 1. 基线条件：如果当前节点是 null，说明已经到底，直接返回。
    if (root === null) {
        return null;
    }

    // 2. 交换当前节点的左右子节点
    // 这里我们先递归处理，再交换，效果是一样的。
    // 也可以先交换，再递归。我们采用先递归后交换的“后序遍历”思路。
    
    // 递归地翻转左子树
    const left = invertTree(root.left);
    // 递归地翻转右子树
    const right = invertTree(root.right);

    // 将已经翻转好的左右子树，再进行交换
    root.left = right;
    root.right = left;
    
    // 3. 返回翻转后的当前节点
    return root;
};

代码执行过程剖析：

我们以上面的树为例，看看 invertTree(node=4) 是如何执行的：

invertTree(4) 被调用。root 不是 null。
invertTree(4.left) 即 invertTree(2) 被调用。
1. invertTree(2) 被调用。root 不是 null。
2. invertTree(2.left) 即 invertTree(1) 被调用。
  1. invertTree(1) 被调用。root 不是 null。
  2. invertTree(1.left) 即 invertTree(null) -> 返回 null。
  3. invertTree(1.right) 即 invertTree(null) -> 返回 null。
  4. 节点 1 的 left 和 right 交换（都是 null），1 本身不变。返回节点 1。
3. invertTree(2.right) 即 invertTree(3) 被调用。（过程同 1）。返回节点 3。
4. 在 invertTree(2) 的上下文中，left 变量接收到返回的 1，right 变量接收到返回的 3。
5. 交换 2 的子节点：2.left 变为 3，2.right 变为 1。返回节点 2。
invertTree(4.right) 即 invertTree(7) 被调用。（过程同 2，最终 7 的左孩子变 9，右孩子变 6）。返回节点 7。
在 invertTree(4) 的上下文中，left 变量接收到返回的、已翻转的节点 2，right 变量接收到返回的、已翻转的节点 7。
交换 4 的子节点：4.left 变为 7，4.right 变为 2。
返回根节点 4。整个树翻转完毕。

这种从下到上翻转的方式，属于深度优先搜索 (DFS) 中的后序遍历。你也可以采用前序遍历的方式（先交换，再递归），效果完全一样。

JavaScript

// 前序遍历的递归实现
var invertTreePreOrder = function(root) {
    if (root === null) {
        return null;
    }
    
    // 1. 先交换
    [root.left, root.right] = [root.right, root.left]; // ES6 解构赋值，更简洁
    
    // 2. 再递归处理子树
    invertTreePreOrder(root.left);
    invertTreePreOrder(root.right);
    
    return root;
};

方法二：迭代解法 (BFS - 广度优先搜索)

虽然递归很直观，但如果树的深度非常大，可能会导致调用栈溢出 (Stack Overflow)。迭代法则没有这个问题。

我们可以使用一个队列 (Queue) 来辅助，这和广度优先搜索 (BFS) 的思路很像。

逻辑推演（迭代思路）

创建一个队列，并把根节点放进去。
当队列不为空时，循环执行以下操作：

a. 从队列中取出一个节点（队首元素），称之为 currentNode。

b. 交换 currentNode 的左右子节点。

c. 如果 currentNode 交换后的左子节点（也就是原来的右子节点）不为 null，就把它加入队列。

d. 如果 currentNode 交换后的右子节点（也就是原来的左子节点）不为 null，也把它加入队列。
当队列为空时，说明树中所有节点都已经被访问并交换过，翻转完成。

JavaScript 实现：

JavaScript

/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTreeIterative = function(root) {
    if (root === null) {
        return null;
    }
    
    // 1. 创建一个队列，并将根节点入队
    const queue = [root];
    
    // 2. 当队列不为空时循环
    while (queue.length > 0) {
        // a. 从队列中取出当前节点
        const currentNode = queue.shift(); // shift() 取出并删除队首元素
        
        // b. 交换当前节点的左右子节点
        [currentNode.left, currentNode.right] = [currentNode.right, currentNode.left];
        
        // c. 如果新的左子节点存在，将其入队，以便后续处理它的子节点
        if (currentNode.left !== null) {
            queue.push(currentNode.left);
        }
        
        // d. 如果新的右子节点存在，将其入队
        if (currentNode.right !== null) {
            queue.push(currentNode.right);
        }
    }
    
    // 3. 返回根节点
    return root;
};

代码执行过程剖析：

queue = [4]
循环 1:
- currentNode = 4 (出队)。queue = []。
- 交换 4 的孩子。树变为：4 -> (7, 2)。
- 4.left (即 7) 不为 null，入队。queue = [7]。
- 4.right (即 2) 不为 null，入队。queue = [7, 2]。
循环 2:
- currentNode = 7 (出队)。queue = [2]。
- 交换 7 的孩子。树变为：7 -> (9, 6)。
- 7.left (即 9) 不为 null，入队。queue = [2, 9]。
- 7.right (即 6) 不为 null，入队。queue = [2, 9, 6]。
循环 3:
- currentNode = 2 (出队)。queue = [9, 6]。
- 交换 2 的孩子。树变为：2 -> (3, 1)。
- 2.left (即 3) 不为 null，入队。queue = [9, 6, 3]。
- 2.right (即 1) 不为 null，入队。queue = [9, 6, 3, 1]。
后续循环:
- 9, 6, 3, 1 会依次出队。因为它们都是叶子节点，它们的 left 和 right 都是 null，交换后依然是 null，所以不会有新节点入队。
队列最终变空，循环结束。返回 root。

4. 复杂度分析与对比

特性	递归解法 (DFS)	迭代解法 (BFS)
时间复杂度	O(N)	O(N)
	我们需要访问树中的每一个节点恰好一次。	我们需要访问树中的每一个节点并将其入队/出队一次。
空间复杂度	O(H)	O(W)
	H 是树的高度。空间消耗主要来自递归调用栈。最坏情况（树退化为链表），H=N，空间为 O(N)。最好情况（完全二叉树），H=logN，空间为 O(logN)。	W 是树的最大宽度。空间消耗主要来自队列。最坏情况（完全二叉树），最后一层节点数最多，约为 N/2，空间为 O(N)。

结论与建议

两种方法都是正确且高效的。

递归解法：代码更少，更简洁，逻辑更贴近问题的递归定义。对于大多数面试和日常应用场景，这都是首选，因为它最能体现你对问题本质的理解。
迭代解法：可以避免在树深度极大时出现调用栈溢出的风险，健壮性更好。在需要处理非常深或结构未知的树时，迭代是更安全的选择。

综合来看，我更推荐使用递归解法。

它不仅代码优雅，而且深刻地反映了树形结构问题的内在特性——一个大问题可以分解为若干个结构相同的子问题。掌握了递归，你就掌握了解决大部分树相关问题的钥匙。

// 二叉树节点的构造函数 function TreeNode(val, left, right) { this.val = val === undefined ? 0 : val; this.left = left === undefined ? null : left; this.right = right === undefined ? null : right; }

/** * 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) { // 1. 基线条件：如果当前节点是 null，说明已经到底，直接返回。 if (root === null) { return null; } // 2. 交换当前节点的左右子节点 // 这里我们先递归处理，再交换，效果是一样的。 // 也可以先交换，再递归。我们采用先递归后交换的“后序遍历”思路。 // 递归地翻转左子树 const left = invertTree(root.left); // 递归地翻转右子树 const right = invertTree(root.right); // 将已经翻转好的左右子树，再进行交换 root.left = right; root.right = left; // 3. 返回翻转后的当前节点 return root; };

// 前序遍历的递归实现 var invertTreePreOrder = function(root) { if (root === null) { return null; } // 1. 先交换 [root.left, root.right] = [root.right, root.left]; // ES6 解构赋值，更简洁 // 2. 再递归处理子树 invertTreePreOrder(root.left); invertTreePreOrder(root.right); return root; };

/** * @param {TreeNode} root * @return {TreeNode} */ var invertTreeIterative = function(root) { if (root === null) { return null; } // 1. 创建一个队列，并将根节点入队 const queue = [root]; // 2. 当队列不为空时循环 while (queue.length > 0) { // a. 从队列中取出当前节点 const currentNode = queue.shift(); // shift() 取出并删除队首元素 // b. 交换当前节点的左右子节点 [currentNode.left, currentNode.right] = [currentNode.right, currentNode.left]; // c. 如果新的左子节点存在，将其入队，以便后续处理它的子节点 if (currentNode.left !== null) { queue.push(currentNode.left); } // d. 如果新的右子节点存在，将其入队 if (currentNode.right !== null) { queue.push(currentNode.right); } } // 3. 返回根节点 return root; };

特性

递归解法 (DFS)

迭代解法 (BFS)

时间复杂度

O(N)

我们需要访问树中的每一个节点恰好一次。

我们需要访问树中的每一个节点并将其入队/出队一次。

空间复杂度

O(H)

O(W)

H 是树的高度。空间消耗主要来自递归调用栈。最坏情况（树退化为链表），H=N，空间为 O(N)。最好情况（完全二叉树），H=logN，空间为 O(logN)。

W 是树的最大宽度。空间消耗主要来自队列。最坏情况（完全二叉树），最后一层节点数最多，约为 N/2，空间为 O(N)。