TypeScript实现二叉树镜像：思路与代码解析

思路分析

获取二叉树的镜像本质上是将树的结构沿中心轴进行翻转。观察镜像前后的变化可知：

• 根节点保持不变。
• 镜像后，原树的左子树变为右子树，原右子树变为左子树。

基于上述规律，我们可以采用先序遍历（Pre-order Traversal）的策略来处理整棵树：访问当前节点时，立即交换其左右子指针。随后，分别对新的左子树和右子树重复此过程，直到所有节点都被处理完毕。这种方法逻辑清晰，且天然适合使用递归实现。

实现代码

在 TypeScript 中，我们需要定义一个二叉树节点类型，并编写递归函数来执行交换操作。以下是核心的实现代码：

export function MirrorImageOfTree(node: BinaryTreeNode | null): void {
  // 1. 边界条件检查：若节点为空，直接返回
  if (node == null) return;
  
  // 2. 终止条件：若为叶子节点，无需交换子节点（虽然交换空值无影响，但提前返回可优化性能）
  if (node.left == null && node.right == null) return;
  
  // 3. 核心步骤：交换左右子节点
  const temp = node.left;
  node.left = node.right;
  node.right = temp;
  
  // 4. 递归处理：对新交换后的左右子树继续执行镜像操作
  if (node.left) {
    MirrorImageOfTree(node.left);
  }
  if (node.right) {
    MirrorImageOfTree(node.right);
  }
}

第 1 步：定义数据结构与初始化

为了验证算法的正确性，我们需要构建一棵具体的二叉树作为测试对象。假设我们要镜像如下结构的树：

const tree: BinaryTreeNode = {
  key: 8,
  left: {
    key: 5,
    left: { key: 3 },
    right: { key: 7 }
  },
  right: { 
    key: 18, 
    left: { key: 13 }, 
    right: { key: 22 } 
  } 
};

该树包含根节点 8，以及深层级的叶子节点。在实际业务或算法题（如 LeetCode）中，这通常对应一个标准的多层二叉树模型。

第 2 步：执行镜像并验证结果

调用之前定义的函数对树进行原地修改（In-place modification）：

MirrorImageOfTree(tree); // 传入需要镜像的根节点
console.log("镜像后的树", tree);

注意：函数签名接受 node: BinaryTreeNode | null，意味着它可以处理空树或单节点树的边缘情况。

执行后，原左侧分支将移动到右侧，原右侧分支移动到左侧。通过控制台输出或可视化图表对比，可以确认所有非叶子节点的子节点引用均已成功互换。

总结

通过递归地进行先序遍历并在每个节点执行左右子树交换，我们能够高效地获取任意二叉树的镜像。这种方式时间复杂度为 O(n)（n 为节点数），空间复杂度取决于递归栈的深度，通常为 O(h)（h 为树的高度）。掌握这一基础数据结构操作，有助于解决更复杂的树形问题。

以上就是TypeScript实现二叉树镜像的详细内容，更多关于TypeScript数据结构与算法的资料请关注本站其它相关文章！