今天給大家講解一道微軟一面的算法題，也是LeetCode第226號題目，反轉二叉樹，就像這樣：

簡單講就是把每個節點的左子樹和右子樹進行交換 。

顯然，這需要我們能夠遍歷該二叉樹。

那么遍歷二叉樹就有兩種經典的解法：深度優先遍歷，Deep First Search，簡稱DFS；另一個是廣度優先遍歷，Breadth First Search，簡稱BFS。

深度優先搜索

顧名思義，深度優先搜索是我總是優先訪問“ 節點的子節點的子節點 。。”，這是什么意思呢？對于給定的二叉樹，我們首先訪問節點4：

接下來訪問4的左子樹2：

再接下來依然訪問2的左子樹1：

1是葉子節點，其左右子樹都為空，因此返回上一個節點2，然后訪問其右子樹3，重復上述過程直到所有節點訪問完畢。

你會發現，這其實是一個遞歸過程：

深度優先搜索非常適合用遞歸代碼編寫。

回到這個題目，代碼就可以這樣寫：

TreeNode* invertTree(TreeNode* root) {
    // 如果是空節點，直接訪問
    if (root == nullptr) return nullptr;
    
    // 找到當前節點的左右字節點，并交換
    auto* left = root->left;
    auto* right = root->right;
    root->left = right;
    root->right = left;
    
    // 處理當前節點的左右子節點
    invertTree(left);
    invertTree(right);
    
    return root;
}

接下來我們看廣度優先搜索。

廣度優先搜索

個人認為廣度優先搜索相對來說更容易理解，通俗的講，廣度優先搜索是“ 先把同輩訪問完再訪問下一輩 ”，因此這一種“ 層級 ”遍歷方法，先是訪問第一層，然后是第二層。。直到最后一層，就像這樣：

在這里我們可以使用一個隊列，先把根節點4放入隊列中，然后從隊列依次取出節點，交換其左右字數，并將該節點的左右字數也放到隊列中，重復上述過程直到隊列為空，用代碼就是這樣實現：

TreeNode* invertTree(TreeNode* root) {
  if (root == nullptr) return nullptr;
  
  // 定義隊列，并把根節點放到隊列中
  queue q;
  q.push(root);
  
  while(!q.empty()) {
    // 從隊列中取出節點
    auto* t = q.front();
    q.pop();

    // 交換該節點的左右子樹
    auto* left = t->left;
    auto* right = t->right;
    t->left = right;
    t->right = left;
    
    // 如果該節點的左右子樹不空則放到隊列
    if (left) q.push(left);
    if (right) q.push(right);
  }
  return root;
}

廣度優先搜索與深度優先搜索不僅僅可以用在二叉樹中，這兩種遍歷方法有著極其廣泛的用途，當我們積攢足夠多的使用案例后將會系統總結這兩種遍歷方法。