[Easy] 翻轉二叉樹 Invert a Binary Tree

翻轉二叉樹 Invert a binary tree 是程式面試中，很常會考的入門考題。在這個面試題中，我們要把下圖左二叉樹，翻轉成下圖右。

可以看到：

• 4 節點底下的 2 與 7 位置對調
• 2 節點底下的 1 與 3 位置對調
• 7 節點底下的 6 與 9 位置對調

     4                 4
   /   \             /   \
  2     7           7     2
 / \   / \         / \   / \
1   3 6   9       9   6 3   1

如何翻轉二叉樹？

要怎麼翻轉一個二叉樹呢？很簡單，我們可以透過遞迴 recursion 的概念。遞迴就是把問題拆解成子問題，然後在函式中呼叫函式自己，來解決子問題。

以翻轉二叉樹來說，我們可以先翻轉 4 底下的 7 與 2。

        4
       / \
      7   2
     / \ / \
    6  9 1  3
// 4 底下的 7 <-> 2 對調

接著利用遞迴的概念，往下走，翻轉 7 底下的 6 與 9。

        4
       / \
      7   2
     / \ / \
    9  6 1  3
// 7 底下的 6 <-> 9 對調

同樣地，翻轉 2 底下的 1 與 3。

        4
       / \
      7   2
     / \ / \
    9  6 3  1
// 2 底下的 1 <-> 3 對調

一步步來看的話，會是這樣。

 原始二叉樹            步驟 2:            步驟 3:            步驟 4:
     4                 4                 4                 4
   /   \             /   \             /   \             /   \
  2     7           7     2           7     2           7     2
 / \   / \         / \   / \         / \   / \         / \   / \
1   3 6   9       6   9 1   3       9   6 1   3       9   6 3   1

翻轉二叉樹 JavaScript 程式碼

接著一起來看看程式碼吧！

// 定義 invertTree 函式，會接收根節點
function invertTree(root) {
  // 設定遞迴終止條件：如果沒有節點就停止，返回 null
  if (root === null) return null;

  // 交換左右子節點，需要一個 temp 變數來暫存 root.left
  const temp = root.left;
  root.left = root.right;
  root.right = temp;

  // 遞迴呼叫 invertTree 自己，分別傳入左右的子節點
  invertTree(root.left);
  invertTree(root.right);

  // 返回根節點
  return root;
}