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

簡(jiǎn)單講就是把每個(gè)節(jié)點(diǎn)的左子樹和右子樹進(jìn)行交換 。

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

那么遍歷二叉樹就有兩種經(jīng)典的解法：深度優(yōu)先遍歷，Deep First Search，簡(jiǎn)稱DFS；另一個(gè)是廣度優(yōu)先遍歷，Breadth First Search，簡(jiǎn)稱BFS。

深度優(yōu)先搜索

顧名思義，深度優(yōu)先搜索是我總是優(yōu)先訪問“ 節(jié)點(diǎn)的子節(jié)點(diǎn)的子節(jié)點(diǎn) 。。”，這是什么意思呢？對(duì)于給定的二叉樹，我們首先訪問節(jié)點(diǎn)4：

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

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

1是葉子節(jié)點(diǎn)，其左右子樹都為空，因此返回上一個(gè)節(jié)點(diǎn)2，然后訪問其右子樹3，重復(fù)上述過程直到所有節(jié)點(diǎn)訪問完畢。

你會(huì)發(fā)現(xiàn)，這其實(shí)是一個(gè)遞歸過程：

深度優(yōu)先搜索非常適合用遞歸代碼編寫。

回到這個(gè)題目，代碼就可以這樣寫：

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

接下來我們看廣度優(yōu)先搜索。

廣度優(yōu)先搜索

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

在這里我們可以使用一個(gè)隊(duì)列，先把根節(jié)點(diǎn)4放入隊(duì)列中，然后從隊(duì)列依次取出節(jié)點(diǎn)，交換其左右字?jǐn)?shù)，并將該節(jié)點(diǎn)的左右字?jǐn)?shù)也放到隊(duì)列中，重復(fù)上述過程直到隊(duì)列為空，用代碼就是這樣實(shí)現(xiàn)：

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

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

廣度優(yōu)先搜索與深度優(yōu)先搜索不僅僅可以用在二叉樹中，這兩種遍歷方法有著極其廣泛的用途，當(dāng)我們積攢足夠多的使用案例后將會(huì)系統(tǒng)總結(jié)這兩種遍歷方法。