翻转二叉树

问题

给定一棵二叉树，将其左右子树交换，得到镜像翻转后的二叉树。

输入:
     4
   /   \
  2     7
 / \   / \
1   3 6   9

输出:
     4
   /   \
  7     2
 / \   / \
9   6 3   1

解答

定义二叉树节点

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

递归实现

function invertTree(root) {
  // 递归终止条件
  if (root === null) {
    return null;
  }

  // 交换左右子节点
  const temp = root.left;
  root.left = root.right;
  root.right = temp;

  // 递归翻转左右子树
  invertTree(root.left);
  invertTree(root.right);

  return root;
}

迭代实现（BFS）

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

  const queue = [root];

  while (queue.length > 0) {
    const node = queue.shift();

    // 交换左右子节点
    [node.left, node.right] = [node.right, node.left];

    // 将子节点加入队列
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }

  return root;
}

测试代码

// 构建测试树
const root = new TreeNode(
  4,
  new TreeNode(2, new TreeNode(1), new TreeNode(3)),
  new TreeNode(7, new TreeNode(6), new TreeNode(9))
);

// 翻转
invertTree(root);

// 验证：root.left.val 应该是 7，root.right.val 应该是 2
console.log(root.left.val);  // 7
console.log(root.right.val); // 2

关键点

• 递归思路：先交换当前节点的左右子节点，再递归处理子树
• 迭代思路：用队列层序遍历，逐个交换每个节点的左右子节点
• 递归终止条件是节点为 null
• 时间复杂度 O(n)，每个节点访问一次
• 空间复杂度：递归是 O(h)（h 为树高），迭代是 O(n)