這道題目是非常經典的題目，也是比較簡單的題目（至少一看就會）。

但正是因為這道題太簡單，一看就會，一些同學都沒有抓住起本質，稀里糊涂的就把這道題目過了。

如果做過這道題的同學也建議認真看完，相信一定有所收獲！

226.翻轉二叉樹題目地址：https://leetcode-cn.com/problems/invert-binary-tree/

翻轉一棵二叉樹。

這道題目背后有一個讓程序員心酸的故事，聽說 Homebrew的作者Max Howell，就是因為沒在白板上寫出翻轉二叉樹，最后被Google拒絕了。（真假不做判斷，權當一個樂子哈）

思路我們之前介紹的都是各種方式遍歷二叉樹，這次要翻轉了，感覺還是有點懵逼。

這得怎么翻轉呢？

如果要從整個樹來看，翻轉還真的挺復雜，整個樹以中間分割線進行翻轉，如圖：

可以發現想要翻轉它，其實就把每一個節點的左右孩子交換一下就可以了。

關鍵在于遍歷順序，前中后序應該選哪一種遍歷順序？（一些同學這道題都過了，但是不知道自己用的是什么順序）

遍歷的過程中去翻轉每一個節點的左右孩子就可以達到整體翻轉的效果。

注意只要把每一個節點的左右孩子翻轉一下，就可以達到整體翻轉的效果

這道題目使用前序遍歷和后序遍歷都可以，唯獨中序遍歷不行，因為中序遍歷會把某些節點的左右孩子翻轉了兩次！建議拿紙畫一畫，就理解了

那么層序遍歷可以不可以呢？依然可以的！只要把每一個節點的左右孩子翻轉一下的遍歷方式都是可以的！

遞歸法對于二叉樹的遞歸法的前中后序遍歷，已經在二叉樹：前中后序遞歸遍歷詳細講解了。

我們下文以前序遍歷為例，通過動畫來看一下翻轉的過程：

我們來看一下遞歸三部曲：

確定遞歸函數的參數和返回值

參數就是要傳入節點的指針，不需要其他參數了，通常此時定下來主要參數，如果在寫遞歸的邏輯中發現還需要其他參數的時候，隨時補充。

返回值的話其實也不需要，但是題目中給出的要返回root節點的指針，可以直接使用題目定義好的函數，所以就函數的返回類型為TreeNode*。

TreeNode* invertTree（TreeNode* root）

確定終止條件

當前節點為空的時候，就返回

if （root == NULL） return root;

確定單層遞歸的邏輯

因為是先前序遍歷，所以先進行交換左右孩子節點，然后反轉左子樹，反轉右子樹。

swap（root-》left， root-》right）;

invertTree（root-》left）;

invertTree（root-》right）;

基于這遞歸三步法，代碼基本寫完，C++代碼如下：

class Solution {public：

TreeNode* invertTree（TreeNode* root） {

if （root == NULL） return root;

swap（root-》left， root-》right）; // 中

invertTree（root-》left）; // 左

invertTree（root-》right）; // 右

return root;

}

};

迭代法深度優先遍歷二叉樹：聽說遞歸能做的，棧也能做！中給出了前中后序迭代方式的寫法，所以本地可以很輕松的切出如下迭代法的代碼：

C++代碼迭代法（前序遍歷）

class Solution {public：

TreeNode* invertTree（TreeNode* root） {

if （root == NULL） return root;

stack《TreeNode*》 st;

st.push（root）;

while（！st.empty（）） {

TreeNode* node = st.top（）; // 中

st.pop（）;

swap（node-》left， node-》right）;

if（node-》right） st.push（node-》right）; // 右

if（node-》left） st.push（node-》left）; // 左

}

return root;

}

};

如果這個代碼看不懂的話可以在回顧一下二叉樹：聽說遞歸能做的，棧也能做！。

我們在二叉樹：前中后序迭代方式的統一寫法中介紹了統一的寫法，所以，本題也只需將文中的代碼少做修改便可。

C++代碼如下迭代法（前序遍歷）

class Solution {public：

TreeNode* invertTree（TreeNode* root） {

stack《TreeNode*》 st;

if （root ！= NULL） st.push（root）;

while （！st.empty（）） {

TreeNode* node = st.top（）;

if （node ！= NULL） {

st.pop（）;

if （node-》right） st.push（node-》right）; // 右

if （node-》left） st.push（node-》left）; // 左

st.push（node）; // 中

st.push（NULL）;

} else {

st.pop（）;

node = st.top（）;

st.pop（）;

swap（node-》left， node-》right）; // 節點處理邏輯

}

}

return root;

}

};

如果上面這個代碼看不懂，回顧一下文章二叉樹：前中后序迭代方式的統一寫法。

廣度優先遍歷也就是層序遍歷，層數遍歷也是可以翻轉這棵樹的，因為層序遍歷也可以把每個節點的左右孩子都翻轉一遍，代碼如下：

class Solution {public：

TreeNode* invertTree（TreeNode* root） {

queue《TreeNode*》 que;

if （root ！= NULL） que.push（root）;

while （！que.empty（）） {

int size = que.size（）;

for （int i = 0; i 《 size; i++） {

TreeNode* node = que.front（）;

que.pop（）;

swap（node-》left， node-》right）; // 節點處理

if （node-》left） que.push（node-》left）;

if （node-》right） que.push（node-》right）;

}

}

return root;

}

};

如果對以上代碼不理解，或者不清楚二叉樹的層序遍歷，可以看這篇二叉樹：層序遍歷登場！

總結針對二叉樹的問題，解題之前一定要想清楚究竟是前中后序遍歷，還是層序遍歷。

二叉樹解題的大忌就是自己稀里糊涂的過了（因為這道題相對簡單），但是也不知道自己是怎么遍歷的。

這也是造成了二叉樹的題目“一看就會，一寫就廢”的原因。

針對翻轉二叉樹，我給出了一種遞歸，三種迭代（兩種模擬深度優先遍歷，一種層序遍歷）的寫法，都是之前我們講過的寫法，融匯貫通一下而已。

大家一定也有自己的解法，但一定要成方法論，這樣才能通用，才能舉一反三！

其他語言版本Java：//DFS遞歸class Solution {

/**

* 前后序遍歷都可以

* 中序不行，因為先左孩子交換孩子，再根交換孩子（做完后，右孩子已經變成了原來的左孩子），再右孩子交換孩子（此時其實是對原來的左孩子做交換）

*/

public TreeNode invertTree（TreeNode root） {

if （root == null） {

return null;

}

invertTree（root.left）;

invertTree（root.right）;

swapChildren（root）;

return root;

}

private void swapChildren（TreeNode root） {

TreeNode tmp = root.left;

root.left = root.right;

root.right = tmp;

}

}

//BFSclass Solution {

public TreeNode invertTree（TreeNode root） {

if （root == null） {return null;}

ArrayDeque《TreeNode》 deque = new ArrayDeque《》（）;

deque.offer（root）;

while （！deque.isEmpty（）） {

int size = deque.size（）;

while （size-- 》 0） {

TreeNode node = deque.poll（）;

swap（node）;

if （node.left ！= null） {deque.offer（node.left）;}

if （node.right ！= null） {deque.offer（node.right）;}

}

}

return root;

}

public void swap（TreeNode root） {

TreeNode temp = root.left;

root.left = root.right;

root.right = temp;

}

}

Python遞歸法：前序遍歷：

class Solution：

def invertTree（self， root： TreeNode） -》 TreeNode：

if not root：

return None

root.left， root.right = root.right， root.left #中

self.invertTree（root.left） #左

self.invertTree（root.right） #右

return root

迭代法：深度優先遍歷（前序遍歷）：

class Solution：

def invertTree（self， root： TreeNode） -》 TreeNode：

if not root：

return root

st = ［］

st.append（root）

while st：

node = st.pop（）

node.left， node.right = node.right， node.left #中

if node.right：

st.append（node.right） #右

if node.left：

st.append（node.left） #左

return root

迭代法：廣度優先遍歷（層序遍歷）：

import collections

class Solution：

def invertTree（self， root： TreeNode） -》 TreeNode：

queue = collections.deque（） #使用deque（）

if root：

queue.append（root）

while queue：

size = len（queue）

for i in range（size）：

node = queue.popleft（）

node.left， node.right = node.right， node.left #節點處理

if node.left：

queue.append（node.left）

if node.right：

queue.append（node.right）

return root

責任編輯：haq