請完成一個函數(shù)，輸入一個二叉樹，該函數(shù)輸出它的鏡像。

例如輸入：

4

/ \

2 7

/ \ / \

1 3 6 9

鏡像輸出：

4

/ \

7 2

/ \ / \

9 6 3 1

示例

• 輸入：root = [4,2,7,1,3,6,9]

• 輸出：[4,7,2,9,6,3,1]

限制

• 0 <= 節(jié)點(diǎn)個數(shù) <= 1000

方法一：遞歸

一點(diǎn)點(diǎn)經(jīng)驗(yàn)：每次看到有關(guān)樹的算法的時候，我腦海里第一個想到的都是“先試試用遞歸可不可以”，閱讀完題目后發(fā)現(xiàn)，no problem！

從根節(jié)點(diǎn)開始，遞歸遍歷整個二叉樹，交換每個節(jié)點(diǎn)的左/右子節(jié)點(diǎn)，就生成它的鏡像了。

算法流程：

• 如果為空（即遍歷葉子節(jié)點(diǎn)），直接返回null；

• 旋轉(zhuǎn)，遞歸左/右子節(jié)點(diǎn)；

• 并將返回值作為當(dāng)前節(jié)點(diǎn)的右/左子節(jié)點(diǎn)；

• 返回當(dāng)前節(jié)點(diǎn)。

代碼如下：

復(fù)雜度分析

• 時間復(fù)雜度：O(N)，其中 N 為二叉樹節(jié)點(diǎn)的數(shù)目。我們會遍歷二叉樹中的每一個節(jié)點(diǎn)，對每個節(jié)點(diǎn)而言，我們在常數(shù)時間內(nèi)交換其兩棵子樹。

• 空間復(fù)雜度：O(N)。使用的空間由遞歸棧的深度決定，它等于當(dāng)前節(jié)點(diǎn)在二叉樹中的高度。在平均情況下，二叉樹的高度與節(jié)點(diǎn)個數(shù)為對數(shù)關(guān)系，即 O(logN)。而在最壞情況下，樹形成鏈狀，空間復(fù)雜度為 O(N)。

方法二：輔助棧（或隊(duì)列）

利用棧（或隊(duì)列）遍歷樹的所有節(jié)點(diǎn)，并交換每個節(jié)點(diǎn)的左/右子節(jié)點(diǎn)。

算法流程：

• 如果為空（即遍歷葉子節(jié)點(diǎn)），直接返回null；

• 把根節(jié)點(diǎn)加入到棧（或隊(duì)列）中；

• 彈出棧（或隊(duì)列）中的根節(jié)點(diǎn)（當(dāng)前節(jié)點(diǎn)）；

• 如果左/右子節(jié)點(diǎn)非空，將左/右子節(jié)點(diǎn)入棧（或隊(duì)列）；

• 交換當(dāng)前節(jié)點(diǎn)的左/右子節(jié)點(diǎn)；

• 當(dāng)棧（或隊(duì)列）為空時返回根節(jié)點(diǎn)。

代碼如下：

復(fù)雜度分析

• 時間復(fù)雜度：O(N)，其中 N 為二叉樹的節(jié)點(diǎn)數(shù)量，建立二叉樹鏡像需要遍歷樹的所有節(jié)點(diǎn)，占用 O(N) 時間。

• 空間復(fù)雜度：O(N)，最差情況下，棧 stack 最多同時存儲

(N+1)/2 個節(jié)點(diǎn)，占用 O(N) 額外空間。

END

遞歸是自下而上交換，棧是自上而下交換。

本文內(nèi)容出處是力扣官網(wǎng)，希望和大家一起刷算法，在后面的路上不變禿但是變強(qiáng)！

好兄弟可以點(diǎn)贊并關(guān)注我的公眾號“javaAnswer”，全部都是干貨。