這是悅樂書的第168次更新，第170篇原創(chuàng)

01 看題和準備

今天介紹的是LeetCode算法題中Easy級別的第27題（順位題號是111）。給定二叉樹，找到它的最小深度。最小深度是沿從根節(jié)點到最近的葉節(jié)點的最短路徑上的節(jié)點數(shù)。葉子節(jié)點是沒有子節(jié)點的節(jié)點。例如：

給定二叉樹[3,9,20，null，null，15,7]，

3/ \9 20/ \15 7

返回其最小深度= 2。

本次解題使用的開發(fā)工具是eclipse，jdk使用的版本是1.8，環(huán)境是win7 64位系統(tǒng)，使用Java語言編寫和測試。

02 第一種解法

之前我們有解過最大深度的題，今天這道題相反，求最短路徑，那是不是直接將原來代碼中的最大改為最小即可？如果你這樣試過，會發(fā)現(xiàn)根本不是那么回事！

特殊情況一：當傳入的二叉樹為空時，最短路徑就是0。

特殊情況二：當傳入的二叉樹只有根節(jié)點時，最短路徑是1.

正常情況：當某一節(jié)點的左子節(jié)點為空時，這時我們需要求其右子節(jié)點的最短路徑；當某一節(jié)點的右子節(jié)點為空時，這時我們需要求其左子節(jié)點的最短路徑；當某一節(jié)點的左子節(jié)點和右子節(jié)點都不為空時，這時我們要求其左子樹和右子樹的最短路徑。

public int minDepth(TreeNode root) {if (root == null) {return 0;}if ((root.left == null) && (root.right == null)) {return 1;}if (root.left == null) {return minDepth(root.right) + 1;}if (root.right == null) {return minDepth(root.left) + 1;}return 1+Math.min(minDepth(root.left), minDepth(root.right)); }

03 第二種解法

除了上面的遞歸外，我們依舊可以使用遍歷的方法。此解法與求最大深度時的第三種解法類似，也是利用隊列，只是多了一步判斷：當左右節(jié)點都為空時，此節(jié)點是葉子節(jié)點，需要更新最短路徑的值。

public int minDepth2(TreeNode root) {if (root == null) {return 0;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);int minDepth = Integer.MAX_VALUE;int depth = 1;while (!queue.isEmpty()) {int size = queue.size(); while (size > 0) {TreeNode t = queue.poll();if (t.left != null) {queue.offer(t.left);}if (t.right != null) {queue.offer(t.right);}if (t.left == null && t.right == null) {minDepth = Math.min(minDepth, depth); }size--;}depth++;}return minDepth; }

04 小結(jié)

以上就是全部內(nèi)容，如果大家有什么好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉(zhuǎn)發(fā)就是對我最大的回報和支持！

轉(zhuǎn)載于:https://www.cnblogs.com/xiaochuan94/p/9943826.html

總結(jié)

以上是生活随笔為你收集整理的LeetCode算法题-Minimum Depth of Binary Tree（Java实现）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。