實(shí)現(xiàn)思路

二叉樹(shù)的鏡像中我們知道了此問(wèn)題的解決方案是前序遍歷，那么我們可以修改下前序遍歷算法，父節(jié)點(diǎn)遍歷后，先遍歷它的右子節(jié)點(diǎn)，再遍歷它的左子節(jié)點(diǎn)，我們把這種算法稱為：對(duì)稱前序遍歷。

如下圖所示的兩棵樹(shù)，我們分別列舉下兩種遍歷的結(jié)果：

樹(shù)A：

• 前序遍歷：8, 6, 5, 7, 6, 7, 5
• 對(duì)稱前序遍歷：8, 6, 5, 7, 6, 7, 5

樹(shù)B：

• 前序遍歷：8, 6, 5, 7, 9, 7, 5
• 對(duì)稱前序遍歷：8, 9, 5, 7, 6, 7, 5

經(jīng)過(guò)對(duì)比后，我們發(fā)現(xiàn)樹(shù)A的兩種遍歷方法得到的結(jié)果是一樣的，那么它就是對(duì)稱的；樹(shù)B的結(jié)果不同，它就不是對(duì)稱的。

如果有一顆不完全二叉樹(shù)，它的所有節(jié)點(diǎn)都相同，他是對(duì)稱的嗎？

針對(duì)于這種情況，我們就需要將它缺省的null節(jié)點(diǎn)進(jìn)行補(bǔ)齊了，補(bǔ)齊后的兩種遍歷結(jié)果為：

• 前序遍歷：7, 7, 7, null, null, 7, null, null, 7, 7, null, null, null
• 對(duì)稱前序遍歷：7, 7, null, 7, null, null, 7, 7, null, null, 7, null, null

對(duì)比兩個(gè)結(jié)果后，我們發(fā)現(xiàn)并不一樣，那么它就不是對(duì)稱的。

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

• 有了思路后，接下來(lái)我們看下代碼實(shí)現(xiàn)，如下所示：
• 從樹(shù)的根節(jié)點(diǎn)出發(fā)，遞歸比對(duì)它的左子節(jié)點(diǎn)和右子節(jié)點(diǎn)

比對(duì)過(guò)程中：

二者都到達(dá)葉子節(jié)點(diǎn)，代表這棵樹(shù)是對(duì)稱的

任意一方到達(dá)葉子結(jié)點(diǎn)，代表這棵樹(shù)不對(duì)稱

節(jié)點(diǎn)值不同，這棵樹(shù)不對(duì)稱

export function SymmetricBinaryTree(node: BinaryTreeNode | null): boolean {
  return isSymmetrical(node, node);
}

function isSymmetrical(
  node: BinaryTreeNode | null | undefined,
  cloneNode: BinaryTreeNode | null | undefined
): boolean {
  // 到達(dá)葉子節(jié)點(diǎn)，兩者都為nul代表節(jié)點(diǎn)相同
  if (node == null && cloneNode == null) {
    return true;
  }
  // 任意一方到達(dá)葉子節(jié)點(diǎn)，代表節(jié)點(diǎn)不同
  if (node == null || cloneNode == null) {
    return false;
  }
  // 節(jié)點(diǎn)值不同
  if (node.key != cloneNode.key) {
    return false;
  }

  // 分別比對(duì)樹(shù)的左子節(jié)點(diǎn)和右子節(jié)點(diǎn)
  return (
    isSymmetrical(node.left, cloneNode.right) &&
    isSymmetrical(node.right, cloneNode.left)
  );
}

接下來(lái)，我們以上個(gè)章節(jié)列舉的例子為例，將其帶入上述代碼，驗(yàn)證下能否正確判斷，如下所示：

const tree: BinaryTreeNode = {
  key: 8,
  left: {
    key: 6,
    left: { key: 5 },
    right: { key: 7 }
  },
  right: { key: 6, left: { key: 7 }, right: { key: 5 } }
};
const isSymmetric = SymmetricBinaryTree(tree);
console.log(tree, "是否為對(duì)稱二叉樹(shù): ", isSymmetric);

示例代碼

本文所用代碼完整版請(qǐng)移步：

• SymmetricBinaryTree
• symmetricBinaryTree-test.ts