每日一道 LeetCode (22)：二叉樹的最大深度
?每天 3 分鐘，走上算法的逆襲之路。
?
前文合集
代碼倉庫
GitHub：https://github.com/meteor1993/LeetCode
Gitee：https://gitee.com/inwsy/LeetCode
題目：二叉樹的最大深度
題目來源：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
給定一個二叉樹，找出其最大深度。
二叉樹的深度為根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長路徑上的節(jié)點(diǎn)數(shù)。
說明:?葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。
示例：給定二叉樹 [3,9,20,null,null,15,7]，
????3
???/?\
??9??20
????/??\
???15???7
返回它的最大深度 3 。
解題思路
經(jīng)過前兩天的訓(xùn)練以及學(xué)習(xí)，看到這道題的第一個反應(yīng)應(yīng)該是這題有兩種做法，一種是遞歸，另一種是迭代。
如果這個都沒想到的同學(xué)，建議重新看下前面兩篇文章，看完以后記得一定要自己手動實(shí)現(xiàn)一遍。
畢竟實(shí)踐出真知。
第一種方法：「遞歸」
關(guān)于如何遞歸我就不多說了，這玩意很難講清楚，更好的方式是自己拿到代碼，多 debug 幾次，自然就理解了，可能這就是天賦？
public?int?maxDepth(TreeNode?root)?{
????if?(root?==?null)?return?0;
????return?Math.max(maxDepth(root.left),?maxDepth(root.right))?+?1;
}
代碼很短，總共就兩行，如果要讓我講清楚這兩行，屬實(shí)有點(diǎn)強(qiáng)人所難。
所以，一切看緣分吧，懂就是懂了。
第二種方法：「迭代」
迭代說白了就是循環(huán)，整體思路會比遞歸好理解很多，當(dāng)然，這種方案代碼也會比遞歸多很多。
首先還是先定義一個隊(duì)列（好像截止目前，所有遇到二叉樹進(jìn)行迭代都是要先搞一個隊(duì)列），把我們的二叉樹放進(jìn)去，然后開始第一個大循環(huán)，直到我們的隊(duì)列里面為空結(jié)束。
注意哦，我們放在隊(duì)列里面的是當(dāng)前層的所有節(jié)點(diǎn)，接下來我們在大循環(huán)里面再做一個小循環(huán)，這個小循環(huán)的作用是遍歷當(dāng)前層所有節(jié)點(diǎn)，看看這些節(jié)點(diǎn)的下一層還有沒有新的節(jié)點(diǎn)，如果還有就拿出來放到隊(duì)列里面，沒有的話就接著下一次循環(huán)。
這解釋的夠清楚了吧，下面是代碼：
public?int?maxDepth_1(TreeNode?root)?{
????if?(root?==?null)?return?0;
????Queue?queue?=?new?LinkedList();
????queue.offer(root);
????int?ans?=?0;
????while?(!queue.isEmpty())?{
????????int?size?=?queue.size();
????????while?(size?>?0)?{
????????????TreeNode?node?=?queue.poll();
????????????if?(node.left?!=?null)?{
????????????????queue.offer(node.left);
????????????}
????????????if?(node.right?!=?null)?{
????????????????queue.offer(node.right);
????????????}
????????????size--;
????????}
????????ans++;
????}
????return?ans;
}
