如何才能夠翻轉(zhuǎn)二叉樹

這道題目是非常經(jīng)典的題目，也是比較簡單的題目（至少一看就會(huì)）。

但正是因?yàn)檫@道題太簡單，一看就會(huì)，一些同學(xué)都沒有抓住起本質(zhì)，稀里糊涂的就把這道題目過了。

如果做過這道題的同學(xué)也建議認(rèn)真看完，相信一定有所收獲！

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

翻轉(zhuǎn)一棵二叉樹。

這道題目背后有一個(gè)讓程序員心酸的故事，聽說 Homebrew的作者M(jìn)ax Howell，就是因?yàn)闆]在白板上寫出翻轉(zhuǎn)二叉樹，最后被Google拒絕了。（真假不做判斷，權(quán)當(dāng)一個(gè)樂子哈）

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

這得怎么翻轉(zhuǎn)呢？

如果要從整個(gè)樹來看，翻轉(zhuǎn)還真的挺復(fù)雜，整個(gè)樹以中間分割線進(jìn)行翻轉(zhuǎn)，如圖：

可以發(fā)現(xiàn)想要翻轉(zhuǎn)它，其實(shí)就把每一個(gè)節(jié)點(diǎn)的左右孩子交換一下就可以了。

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

遍歷的過程中去翻轉(zhuǎn)每一個(gè)節(jié)點(diǎn)的左右孩子就可以達(dá)到整體翻轉(zhuǎn)的效果。

注意只要把每一個(gè)節(jié)點(diǎn)的左右孩子翻轉(zhuǎn)一下，就可以達(dá)到整體翻轉(zhuǎn)的效果

這道題目使用前序遍歷和后序遍歷都可以，唯獨(dú)中序遍歷不行，因?yàn)橹行虮闅v會(huì)把某些節(jié)點(diǎn)的左右孩子翻轉(zhuǎn)了兩次！建議拿紙畫一畫，就理解了

那么層序遍歷可以不可以呢？依然可以的！只要把每一個(gè)節(jié)點(diǎn)的左右孩子翻轉(zhuǎn)一下的遍歷方式都是可以的！

遞歸法對于二叉樹的遞歸法的前中后序遍歷，已經(jīng)在二叉樹：前中后序遞歸遍歷詳細(xì)講解了。

我們下文以前序遍歷為例，通過動(dòng)畫來看一下翻轉(zhuǎn)的過程：

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

確定遞歸函數(shù)的參數(shù)和返回值

參數(shù)就是要傳入節(jié)點(diǎn)的指針，不需要其他參數(shù)了，通常此時(shí)定下來主要參數(shù)，如果在寫遞歸的邏輯中發(fā)現(xiàn)還需要其他參數(shù)的時(shí)候，隨時(shí)補(bǔ)充。

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

TreeNode* invertTree（TreeNode* root）

確定終止條件

當(dāng)前節(jié)點(diǎn)為空的時(shí)候，就返回

if （root == NULL） return root;

確定單層遞歸的邏輯

因?yàn)槭窍惹靶虮闅v，所以先進(jìn)行交換左右孩子節(jié)點(diǎn)，然后反轉(zhuǎn)左子樹，反轉(zhuǎn)右子樹。

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;

}

};

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

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;

}

};

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

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

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）; // 節(jié)點(diǎn)處理邏輯

}

}

return root;

}

};

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

廣度優(yōu)先遍歷也就是層序遍歷，層數(shù)遍歷也是可以翻轉(zhuǎn)這棵樹的，因?yàn)閷有虮闅v也可以把每個(gè)節(jié)點(diǎn)的左右孩子都翻轉(zhuǎn)一遍，代碼如下：

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）; // 節(jié)點(diǎn)處理

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

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

}

}

return root;

}

};

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

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

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

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

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

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

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

/**

* 前后序遍歷都可以

* 中序不行，因?yàn)橄茸蠛⒆咏粨Q孩子，再根交換孩子（做完后，右孩子已經(jīng)變成了原來的左孩子），再右孩子交換孩子（此時(shí)其實(shí)是對原來的左孩子做交換）

*/

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

迭代法：深度優(yōu)先遍歷（前序遍歷）：

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

迭代法：廣度優(yōu)先遍歷（層序遍歷）：

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 #節(jié)點(diǎn)處理

if node.left：

queue.append（node.left）

if node.right：

queue.append（node.right）

return root

責(zé)任編輯：haq