Invert Binary Tree（翻转二叉树）

题目 / Problem

中文： 给定一棵二叉树的根节点 root，翻转这棵二叉树，并返回它的根节点。

翻转二叉树是指交换树中每个节点的左子树和右子树。
Inverting a binary tree means swapping the left and right subtrees of every node.

English: Given the root of a binary tree, invert the tree, and return its root.

示例 / Examples

Example 1

Input:  root = [4, 2, 7, 1, 3, 6, 9]
Output: [4, 7, 2, 9, 6, 3, 1]

翻转前 / Before:              翻转后 / After:

        4                              4
      /   \                          /   \
     2     7                        7     2
    / \   / \                      / \   / \
   1   3 6   9                    9   6 3   1

Example 2

Input:  root = [2, 1, 3]
Output: [2, 3, 1]

翻转前 / Before:              翻转后 / After:

        2                              2
       / \                            / \
      1   3                          3   1

Example 3

Input:  root = []
Output: []

约束 / Constraints

• 树中的节点数在 [0, 100] 范围内。
  The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

解题思路：递归深度优先搜索 / Approach: Recursive DFS

二叉树的结构天然适合使用递归处理。对于每个节点：
The recursive structure of a binary tree makes recursion a natural solution. For each node:

1. 如果当前节点为 null，直接返回 null。
   If the current node is null, return null.
2. 交换当前节点的左子节点和右子节点。
   Swap the node's left and right children.
3. 递归翻转交换后的左子树和右子树。
   Recursively invert the swapped left and right subtrees.
4. 返回当前节点。
   Return the current node.

只要对每个节点执行一次左右交换，整棵树就会完成镜像翻转。
Once the children of every node have been swapped, the entire tree becomes its mirror image.

JavaScript 实现 / JavaScript Implementation

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *   this.val = val ?? 0;
 *   this.left = left ?? null;
 *   this.right = right ?? null;
 * }
 */

/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
function invertTree(root) {
  if (root === null) {
    return null;
  }

  [root.left, root.right] = [root.right, root.left];

  invertTree(root.left);
  invertTree(root.right);

  return root;
}

执行过程 / Walkthrough

以 root = [4, 2, 7, 1, 3, 6, 9] 为例：
For root = [4, 2, 7, 1, 3, 6, 9]:

叶子节点 1、3、6、9 的左右子节点均为 null，交换后保持不变。最终得到 [4, 7, 2, 9, 6, 3, 1]。
Leaf nodes 1, 3, 6, and 9 have two null children, so swapping them has no visible effect. The final result is [4, 7, 2, 9, 6, 3, 1].

复杂度 / Complexity

设树中共有 n 个节点，树的高度为 h。
Let the tree contain n nodes and have height h.

• 时间复杂度：O(n)，每个节点恰好访问一次。
  Time: O(n), because every node is visited exactly once.
• 空间复杂度：O(h)，递归调用栈的深度等于树的高度。
  Space: O(h), because the recursion depth equals the height of the tree.
  • 平衡二叉树中为 O(log n)。
    It is O(log n) for a balanced binary tree.
  • 最坏情况下，树退化为链表，空间复杂度为 O(n)。
    In the worst case, the tree is skewed and the space complexity is O(n).

迭代解法：广度优先搜索 / Iterative Approach: BFS

也可以使用队列逐层访问所有节点。每次从队列中取出一个节点，交换它的左右子节点，再将非空子节点加入队列。
A queue can also be used to visit every node level by level. Dequeue a node, swap its children, and enqueue each non-null child.

function invertTreeIterative(root) {
  if (root === null) {
    return null;
  }

  const queue = [root];
  let front = 0;

  while (front < queue.length) {
    const node = queue[front++];

    [node.left, node.right] = [node.right, node.left];

    if (node.left !== null) queue.push(node.left);
    if (node.right !== null) queue.push(node.right);
  }

  return root;
}

• 时间复杂度 / Time: O(n)
• 空间复杂度 / Space: O(n)，队列最坏情况下需要保存一层中的大量节点。
  In the worst case, the queue may hold many nodes from one level.

这里使用索引 front 读取队列，没有调用 shift()，避免了 JavaScript 数组每次移动剩余元素的额外开销。
An index named front is used instead of shift(), avoiding the extra cost of moving the remaining JavaScript array elements on every dequeue operation.

易错点 / Common Pitfalls

• 空树 root = null 应直接返回 null。
  Return null immediately when the tree is empty.
• 必须交换每一个节点的左右子树，而不只是根节点。
  Swap the subtrees of every node, not only those of the root.
• 翻转操作会直接修改原二叉树。
  The inversion modifies the original tree in place.
• 递归时要确保左右子树都被处理。
  Make sure both subtrees are processed recursively.
• 返回的是根节点 root，而不是某个子节点。
  Return the root node, not one of its children.