侧边栏壁纸
博主头像
神奇的程序员

今天的努力只为未来

  • 累计撰写 143 篇文章
  • 累计创建 25 个标签
  • 累计收到 48 条评论

目 录CONTENT

文章目录

二叉树的镜像

神奇的程序员
2022-07-17 / 0 评论 / 1 点赞 / 194 阅读 / 982 字 正在检测是否收录...

前言

给定一颗二叉树,如何获取它的镜像?本文将跟大家分享这个问题的解决方案,欢迎各位感兴趣的开发者阅读本文。

思路分析

当我们把一张写有文字的纸放在镜子前面,你看到的内容正好与你写的内容是相反的。那么我们就可以依据照镜子的经验画出它的镜像了,如下所示:

  • 镜像前后的两棵树根节点相同
  • 镜像后的树与镜像前相比:它们的左、右子节点交换了位置

image-20220713220838785

通过观察后,我们就得出了一颗树的镜像过程:先序遍历这棵树的每个节点,如果遍历到的节点有子节点,就交换它的两个子节点。当交换完所有非叶节点的左、右子节点之后,就得到了树的镜像。

对树的遍历不了解的开发者,请移步我的另一篇文章:先序遍历

实现代码

想清楚思路后,我们就可以很顺利的写出代码了,如下所示:

export function MirrorImageOfTree(node: BinaryTreeNode | null): void {
  if (node == null) return;
  if (node.left == null && node.right == null) return;
  // 交换左右子节点
  const temp = node.left;
  node.left = node.right;
  node.right = temp;
  if (node.left) {
    MirrorImageOfTree(node.left);
  }
  if (node.right) {
    MirrorImageOfTree(node.right);
  }
}

完整代码请移步:MirrorImageOfTree.ts

我们将文章开头所讲的例子代入上述代码来测试下,如下所示:

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

MirrorImageOfTree(null);
console.log("镜像后的树", tree);

image-20220717114620029

完整代码请移步:mirrorImage-test.ts

写在最后

至此,文章就分享完毕了。

我是神奇的程序员,一位前端开发工程师。

如果你对我感兴趣,请移步我的个人网站,进一步了解。

  • 文中如有错误,欢迎在评论区指正,如果这篇文章帮到了你,欢迎点赞和关注😊
  • 本文首发于神奇的程序员公众号,未经许可禁止转载💌
1

评论区