概要
本篇介紹一下關(guān)于二叉樹結(jié)構(gòu)很基礎(chǔ)的面試題，基礎(chǔ)到什么程度呢，引用谷歌的話術(shù)： 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.（連二叉樹翻轉(zhuǎn)你都不會(huì)，你還玩?zhèn)€毛?。┻M(jìn)一步說明了學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的重要性——為了不被谷歌鄙視-.-
華為面試題——將二叉樹的兩個(gè)孩子換位置，即左變右，右變左。不能用遞規(guī)。
原題
226. Invert Binary Tree（Easy)
Invert a binary tree.
Example:
Input:
Output:
Trivia:
This problem was inspired by this original tweet by Max Howell:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.
226. 翻轉(zhuǎn)二叉樹 （簡單）
翻轉(zhuǎn)一棵二叉樹。
示例：
輸入：
輸出：
備注:
這個(gè)問題是受到 Max Howell 的原問題啟發(fā)：
谷歌：
我們谷歌90％的工程師使用你寫的軟件(Homebrew)，但是你卻無法在面試時(shí)在白板上寫出翻轉(zhuǎn)二叉樹這道題，這...（連二叉樹翻轉(zhuǎn)你都不會(huì)，你還玩?zhèn)€毛?。?- 分類：樹(tree)
分析
理解遞歸思想的條件下很容易想到解題思路，當(dāng)然可能有人會(huì)有疑問，那什么情況下知道使用遞歸呢，有個(gè)最簡單的辦法如果算法里需要重復(fù)循環(huán)用同一個(gè)思路執(zhí)行得到結(jié)果，那么必然可以使用遞歸。進(jìn)行翻轉(zhuǎn)本質(zhì)上可以拆分為兩步遞歸，遞歸翻轉(zhuǎn)左子樹和遞歸翻轉(zhuǎn)右子樹分。無論是否使用遞歸本質(zhì)思想是一致的，使用非遞歸的方式則需要借助使用?；蛘哧?duì)列的結(jié)構(gòu)進(jìn)行存儲(chǔ)未交換的子節(jié)點(diǎn)。
思路設(shè)計(jì)
方法一：循環(huán)，棧存儲(chǔ)（DFS，非遞歸)
本質(zhì)思想是，左右節(jié)點(diǎn)進(jìn)行交換，循環(huán)翻轉(zhuǎn)每個(gè)節(jié)點(diǎn)的左右子節(jié)點(diǎn)，將未翻轉(zhuǎn)的子節(jié)點(diǎn)存入棧中，循環(huán)直到棧里所有節(jié)點(diǎn)都循環(huán)交換完為止。方法一偽代碼：
方法二：循環(huán)，隊(duì)列存儲(chǔ)（BFS，非遞歸）
本質(zhì)思想是，左右節(jié)點(diǎn)進(jìn)行交換，循環(huán)翻轉(zhuǎn)每個(gè)節(jié)點(diǎn)的左右子節(jié)點(diǎn)，將未翻轉(zhuǎn)的子節(jié)點(diǎn)存入隊(duì)列中，循環(huán)直到棧里所有節(jié)點(diǎn)都循環(huán)交換完為止。
- 方法一、方法二偽代碼：
1、判斷根結(jié)點(diǎn)是否為空，為空則返回null；
2、新建棧（隊(duì)列），用于節(jié)點(diǎn)存儲(chǔ)，初始存入根節(jié)點(diǎn)到棧（隊(duì)列）里；
3、while循環(huán)，棧（隊(duì)列）為空時(shí)結(jié)束循環(huán)；
i.出棧（隊(duì)列）一個(gè)節(jié)點(diǎn)，將該節(jié)點(diǎn)的左右子節(jié)點(diǎn)交互；
ii.判斷左右子節(jié)點(diǎn)是否為null，非null則繼續(xù)將左右節(jié)點(diǎn)入棧（隊(duì)列）；
4、循環(huán)交換結(jié)束，返回根節(jié)點(diǎn);
方法三：遞歸
本質(zhì)思想也是左右節(jié)點(diǎn)進(jìn)行交換，交換前遞歸調(diào)用對(duì)根結(jié)點(diǎn)的左右節(jié)點(diǎn)分別進(jìn)行處理，保證交換前左右節(jié)點(diǎn)已經(jīng)翻轉(zhuǎn)。
- 方法三偽代碼：
1、判斷根結(jié)點(diǎn)是否為空，為空則返回null；
2、交換跟節(jié)點(diǎn)的左右節(jié)點(diǎn)；
3、遞歸交互左右子樹；
編碼實(shí)踐
棧實(shí)現(xiàn)
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()) {
final TreeNode node = stack.pop();
final TreeNode left = node.left;
node.left = node.right;
node.right = left;
if(node.left != null) {
stack.push(node.left);
}
if(node.right != null) {
stack.push(node.right);
}
}
return root;
}
隊(duì)列實(shí)現(xiàn)
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
TreeNode left = node.left;
node.left = node.right;
node.right = left;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
return root;
}
遞歸實(shí)現(xiàn)
public TreeNode invertTree(TreeNode node) {
if (node == null) {
return null;
}
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
invertTree(node.left);
invertTree(node.right);
return node;
}
彩蛋
對(duì)比三種實(shí)現(xiàn)代碼執(zhí)行結(jié)果會(huì)發(fā)現(xiàn)，三種方法最終leetcode測評(píng)的效率都是100%，但是方法一的runtime時(shí)間確實(shí)1ms，而方法二和方法三的runtime卻是0ms。為什么同樣的算法思想使用不同的數(shù)據(jù)結(jié)構(gòu)，使用Stack比使用LinkedList要慢呢？這便是本篇的彩蛋！
結(jié)語
華為面試題中的二叉樹翻轉(zhuǎn)使用非遞歸實(shí)現(xiàn)是一道基礎(chǔ)知識(shí)題，二叉樹的左右子節(jié)點(diǎn)翻轉(zhuǎn)的非遞歸實(shí)現(xiàn)也包含了DFS和BFS的使用，最后如果覺得本篇對(duì)你有所幫助，給個(gè)贊吧0.0～
