TypeScript獲取二叉樹(shù)的鏡像實(shí)例

更新時(shí)間：2022年09月26日 11:12:20 作者：神奇的程序員

這篇文章主要為大家介紹了TypeScript獲取二叉樹(shù)的鏡像實(shí)例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

前言

給定一顆二叉樹(shù)，如何獲取它的鏡像？本文將跟大家分享這個(gè)問(wèn)題的解決方案，歡迎各位感興趣的開(kāi)發(fā)者閱讀本文。

思路分析

當(dāng)我們把一張寫(xiě)有文字的紙放在鏡子前面，你看到的內(nèi)容正好與你寫(xiě)的內(nèi)容是相反的。那么我們就可以依據(jù)照鏡子的經(jīng)驗(yàn)畫(huà)出它的鏡像了，如下所示：

鏡像前后的兩棵樹(shù)根節(jié)點(diǎn)相同
鏡像后的樹(shù)與鏡像前相比：它們的左、右子節(jié)點(diǎn)交換了位置

通過(guò)觀察后，我們就得出了一顆樹(shù)的鏡像過(guò)程：先序遍歷這棵樹(shù)的每個(gè)節(jié)點(diǎn)，如果遍歷到的節(jié)點(diǎn)有子節(jié)點(diǎn)，就交換它的兩個(gè)子節(jié)點(diǎn)。當(dāng)交換完所有非葉節(jié)點(diǎn)的左、右子節(jié)點(diǎn)之后，就得到了樹(shù)的鏡像。

對(duì)樹(shù)的遍歷不了解的開(kāi)發(fā)者，請(qǐng)移步我的另一篇文章：先序遍歷

實(shí)現(xiàn)代碼

想清楚思路后，我們就可以很順利的寫(xiě)出代碼了，如下所示：

export function MirrorImageOfTree(node: BinaryTreeNode | null): void {
  if (node == null) return;
  if (node.left == null && node.right == null) return;
  // 交換左右子節(jié)點(diǎn)
  const temp = node.left;
  node.left = node.right;
  node.right = temp;
  if (node.left) {
    MirrorImageOfTree(node.left);
  }
  if (node.right) {
    MirrorImageOfTree(node.right);
  }
}

完整代碼請(qǐng)移步：MirrorImageOfTree.ts

我們將文章開(kāi)頭所講的例子代入上述代碼來(lái)測(cè)試下，如下所示：

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("鏡像后的樹(shù)", tree);