解析LeetCode第226號題目：反轉(zhuǎn)二叉樹

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

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

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

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

深度優(yōu)先搜索

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

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

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

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

你會發(fā)現(xiàn)，這其實是一個遞歸過程：

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

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

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

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

廣度優(yōu)先搜索

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

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

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

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

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