[演算法題目] Invert Binary Tree

本題資訊

難度：medium
使用語言：C++
相關概念：Binary Tree

題目敘述

Write a function that takes in a Binary Tree and inverts it. In other words, the function should swap every left node in the tree for its corresponding right node.
Each BinaryTree node has an integer value, a left child node, and a right child node. Children nodes can either b BinaryTree nodes themselves or None/null.

要將整棵 Binary Tree 翻轉的題目。

Idea 1

首先注意到除了 root 不需要翻轉之外，幾乎所有節點都來個左右大遷移，不過所在層數不會變動。左右變換的概念應該跟 swap 差不多，可以觀察到若 swap 某兩個 parent，下方的分支也必須整株一起動。從 root 開始左右交換子節點，再繼續往下執行一樣動作，直到達到最底端。

原先以為這題想法轉程式碼會比較困難，結果可能是因為有 swap 可以用的關係，實作寫起來反而比難度 easy 更簡單一些。

#include <vector>
using namespace std;

class BinaryTree {
public:
  int value;
  BinaryTree *left;
  BinaryTree *right;

  BinaryTree(int value);
};

void invertBinaryTree(BinaryTree *tree) {
  if (tree == nullptr){
    return;
  }
  swap(tree->left, tree->right);
  invertBinaryTree(tree->left);
  invertBinaryTree(tree->right);
}

時間複雜度：\(O(n)\)，\(n\) 是樹的節點數。
空間複雜度：\(O(h)\)，\(h\) 是樹的高度（或稱深度 depth）。

Idea 2

另外一種方式是使用 queue 的概念去實作，也是一樣有 swap 的概念，一樣很簡單。

#include <vector>
using namespace std;

class BinaryTree {
public:
  int value;
  BinaryTree *left;
  BinaryTree *right;

  BinaryTree(int value);
};

void invertBinaryTree(BinaryTree *tree) {
  queue<BinaryTree*> tmp;
  tmp.push(tree);
  
  while(!tmp.empty()){
    BinaryTree *currentTree = tmp.front();
    tmp.pop();
    swap(currentTree->left, currentTree->right);
    
    if (currentTree->left){
      tmp.push(currentTree->left);
    }
    if (currentTree->right){
      tmp.push(currentTree->right);
    }
  }
}

時間複雜度：\(O(n)\)，\(n\) 是樹的節點數。
空間複雜度：\(O(n)\)。