problem

輸入為一個二元樹，將它左右反轉後回傳。

二元樹如下結構，每一個 BinaryTree 節點有一個整數值 value，左子節點 left，右子節點 right。子節點可能為其他 BinaryTree 節點或為空值。

class BinaryTree {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

sample input:
  tree = 1
     /  \
    2   3
    /  \  /  \
   4    5  6  7
    /  \
   8    9
sample output:
  tree = 1
     /  \
     3   2
    /  \  /  \
   7    6  5  4
         /  \
        9    8

solution 01

將一個二元樹左右對稱反轉，其實也可以理解為將所有的左節點與對應的右節點交換。第一種方式是對樹以廣度優先搜尋的方式遍歷，這樣就可以逐層操作左右節點。
步驟是：

1. 將根節點加入一個佇列 (queue) 中。
2. 佇列不為空的情況下，將節點移除，移除時，如果節點不為空，將該節點的兩個子節點交換，並將子節點加入到佇列中。移除時如果節點為空則不做任何操作。
3. 最後回傳二元樹。

若二元樹中節點總數為 n，
time: O(n)
space: O(n) 因為是逐層操作節點，所以佇列在儲存最底層的所有葉節點時會用到最多空間，而在 (平衡的) 樹中葉節點數量略等於 n / 2，所以空間複雜度為 O(n)。

function invertBinaryTree(tree) {
  const queue = [tree];
  while (queue.length > 0) {
    const current = queue.shift();
    if (current === null) continue;
    swapNodes(current);
    queue.push(current.left);
    queue.push(current.right);
  }
  return tree;
}

function swapNodes(node) {
  let temp = node.left;
  node.left = node.right;
  node.right = temp;
}

solution 02

第二種是遞迴的解法，作法是從根節點開始，交換它的兩個子節點，接下來對子節點重複同樣步驟，也就是相當於不斷以同樣方式操作較小的二元樹。

若二元樹中節點總數為 n，樹的高度為 h，
time: O(n)
space: O(h) 因為每個節點會對子節點呼叫遞迴式，所以呼叫堆疊會用 h 空間。

function invertBinaryTree(tree) {
  if (tree === null) return;
  swapNodes(tree);
  invertBinaryTree(tree.left);
  invertBinaryTree(tree.right);
}

function swapNodes(node) {
  let temp = node.left;
  node.left = node.right;
  node.right = temp;
}