引子：五分鐘玩轉(zhuǎn)面試考點(diǎn)-數(shù)據(jù)結(jié)構(gòu)系列，不會(huì)像那種嚴(yán)肅、古板的教科書(shū)般的博客文章揽祥，而是將晦澀難懂的概念和知識(shí)點(diǎn)盡可能幽默的細(xì)說(shuō)出來(lái)，或結(jié)合生活場(chǎng)景檩电，或從零開(kāi)始分析拄丰。帶給大家一個(gè)嚴(yán)肅而不失風(fēng)趣的數(shù)據(jù)結(jié)構(gòu)。
向上的路俐末，其實(shí)并不擁擠料按，擁擠是因?yàn)椋蟛糠秩诉x擇了安逸...
這幾天練了一下數(shù)據(jù)結(jié)構(gòu)的算法卓箫，腦袋疼载矿，而且整的我有點(diǎn)懷疑人生了...
那廢話不多說(shuō)，咱們進(jìn)行練習(xí)吧烹卒。
1闷盔、操作給定的二叉樹(shù)，將其變換為源二叉樹(shù)的鏡像（二叉樹(shù)左右節(jié)點(diǎn)交換位置）旅急。
說(shuō)實(shí)話逢勾，拿到這道題的時(shí)候，我腦子里就想到了層級(jí)遍歷藐吮。層級(jí)遍歷使用的是隊(duì)列溺拱，可以一層一層的處理數(shù)據(jù)。
public void Mirror(TreeNode root) {
if (root == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (queue.size() != 0) {
//小世界
TreeNode pollNode = queue.poll();
TreeNode lRoot = pollNode.left;
pollNode.left = pollNode.right;
pollNode.right = lRoot;
if (pollNode.left != null)
queue.offer(pollNode.left); //左邊保存
if (pollNode.right != null)
queue.offer(pollNode.right); //右邊保存
}
}
原理就是：使用一個(gè)隊(duì)列queue谣辞，將根節(jié)點(diǎn)保存到隊(duì)列中迫摔，然后將根節(jié)點(diǎn)取出之后，獲取左右兩子樹(shù)后泥从，然后交換位置攒菠。再放入隊(duì)列中。
public void Mirror(TreeNode root) {
//遞歸出口
if (root == null) {
return;
}
//遞歸邏輯(交換)
TreeNode tempNode = root.left;
root.left = root.right;
root.right = tempNode;
//先統(tǒng)一處理左子樹(shù)歉闰，在統(tǒng)一處理右子樹(shù)辖众，在處理右子樹(shù)。
Mirror(root.left);
Mirror(root.right);
}
于是我就問(wèn)自己和敬，如何才能使用遞歸將這個(gè)代碼寫(xiě)出來(lái)呢凹炸？
遞歸出口：程序在極端情況下的返回，一般需要終止遞歸調(diào)用代碼昼弟；
遞歸返回值：程序運(yùn)行一次到底想要返回什么值啤它。我們使用遞歸。明顯就是拿到返回值之后再進(jìn)行算法處理。
內(nèi)部邏輯：每一次方法調(diào)用要執(zhí)行的邏輯操作变骡，會(huì)影響遞歸的返回值离赫。
極端情況？
若是參數(shù)為null塌碌，那么直接返回渊胸；
返回值為void？
那么我們要考慮台妆，我們內(nèi)部的邏輯是什么翎猛？
我們其實(shí)是使用的前序遍歷的思想。第一次獲取根節(jié)點(diǎn)的時(shí)候接剩，將左右子樹(shù)反轉(zhuǎn)切厘，第二次獲取根節(jié)點(diǎn)...第三次獲取根節(jié)點(diǎn)...小胖有點(diǎn)蒙了，我反轉(zhuǎn)了3次懊缺？PS：我是不是有點(diǎn)傻~第三次獲取根節(jié)點(diǎn)的時(shí)候反轉(zhuǎn)左右子樹(shù)就可以啦 后序遍歷疫稿。
public void Mirror(TreeNode root) {
//遞歸出口
if (root == null) {
return;
}
//遞歸邏輯(交換)
//先統(tǒng)一處理左子樹(shù)，在統(tǒng)一處理右子樹(shù)鹃两，在處理右子樹(shù)遗座。
Mirror(root.left);
Mirror(root.right);
TreeNode tempNode = root.left;
root.left = root.right;
root.right = tempNode;
}
2、求樹(shù)的深度怔毛？
首先咱們要明白员萍，樹(shù)的高度=左右兩子樹(shù)最大高度+1。
極端情況拣度？
如果上送的是null碎绎，那么直接返回0；
返回值為int抗果？樹(shù)的最大高度筋帖？
計(jì)算高度，我們要訪問(wèn)左子樹(shù)冤馏，求左子樹(shù)的最大高度日麸；在訪問(wèn)右子樹(shù)，求右子樹(shù)的最大高度逮光，最后將最大高度+1代箭。后序遍歷。左子樹(shù)也是一棵樹(shù)涕刚，右子樹(shù)也是一棵樹(shù)嗡综。
public int TreeDepth(TreeNode root) {
//遞歸出口
if (root == null) {
return 0;
}
//邏輯運(yùn)算
int leftDepth = TreeDepth(root.left); //左子樹(shù)高度
int rightDepth = TreeDepth(root.right); //右子樹(shù)高度
return 1+Math.max(leftDepth, rightDepth); //返回左右子樹(shù)最大值
}
非遞歸就是層級(jí)遍歷，每次指針到底同層的最右元素時(shí)杜漠，將隊(duì)列長(zhǎng)度保存起來(lái)（下一層的最大寬度极景，然后高度+1察净，指針清0）。
public int TreeDepth(TreeNode root) {
//層級(jí)遍歷盼樟，每一層遍歷完畢氢卡，在遍歷下一層；
//在每一層最右元素的位置時(shí)晨缴，隊(duì)列里面保存的是下一層所有節(jié)點(diǎn)數(shù),
// 每遍歷一個(gè)元素count++译秦，若是最后一個(gè)元素nextCount++，此時(shí)depthCount++
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int count = 0; //指針位置[0-curCount]
int curCount = 1; //當(dāng)前節(jié)點(diǎn)總個(gè)數(shù)
int depthCount = 0; //層級(jí)深度
while (queue.size() != 0) {
count++; //沒(méi)運(yùn)行一次喜庞，指針加一
TreeNode treeNode = queue.poll(); //取出頭結(jié)點(diǎn)
if (treeNode.left != null)
queue.offer(treeNode.left);
if (treeNode.right != null)
queue.offer(treeNode.right);
//當(dāng)層級(jí)-最右元素poll出來(lái)之后诀浪，
if (count == curCount) {
count = 0; //指針恢復(fù)出廠設(shè)置
curCount = queue.size(); //當(dāng)前層級(jí)設(shè)置為下一級(jí)
depthCount++; //深度+1
}
}
return depthCount;
}
