個(gè)人認(rèn)為這么一個(gè)層序遍歷的章節(jié)放這么多基本一樣的題目算是很沒意思的了?

填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)節(jié)點(diǎn)和二叉樹最大深度和前面的代碼幾乎完全一樣，所以我就跳過了

代碼隨想錄 (programmercarl.com)

代碼隨想錄 (programmercarl.com)

111.二叉樹的最小深度

給定一個(gè)二叉樹，找出其最小深度。

最小深度是從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量。

說明：葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。

示例 1：

輸入：root = [3,9,20,null,null,15,7]
輸出：2

示例 2：

輸入：root = [2,null,3,null,4,null,5,null,6]
輸出：5

提示：

• 樹中節(jié)點(diǎn)數(shù)的范圍在?[0, 105]?內(nèi)
• -1000 <= Node.val <= 1000

思路

這道題目如果還用層序遍歷去做的話基本就是在模板上面略作修改即可，我在這道題目上關(guān)注的還是它的遞歸解法也就是深度優(yōu)先搜索。

這道題目要找一個(gè)深度最淺的葉子節(jié)點(diǎn)，即左右兒子皆為空，所以我們的遞歸結(jié)束條件即為left==right==null，而我們又需要找一個(gè)最淺的，所以當(dāng)左右兩側(cè)節(jié)點(diǎn)均非空時(shí)，遞歸的返回值應(yīng)當(dāng)是分別對(duì)兩者進(jìn)行遞歸后的較小值加1.

class Solution {public int minDepth(TreeNode root) {if(root==null){return 0;}if(root.left==null&&root.right==null){return 1;}int m1=minDepth(root.left);int m2=minDepth(root.right);if(root.left==null||root.right==null){return m1+m2+1;}return (m1>m2?m2:m1)+1;}
}

其中，若是節(jié)點(diǎn)有一個(gè)兒子為空，則直接返回非空遞歸值加一即可。

層序遍歷總結(jié)

層序遍歷的思路就是將當(dāng)前層的節(jié)點(diǎn)加入隊(duì)列，然后將隊(duì)首的子節(jié)點(diǎn)加入隊(duì)尾，再將隊(duì)首出隊(duì)，不斷循環(huán)直到隊(duì)列為空。

public void checkFun02(TreeNode node) {if (node == null) return;Queue<TreeNode> que = new LinkedList<TreeNode>();que.offer(node);while (!que.isEmpty()) {List<Integer> itemList = new ArrayList<Integer>();int len = que.size();while (len > 0) {TreeNode tmpNode = que.poll();itemList.add(tmpNode.val);if (tmpNode.left != null) que.offer(tmpNode.left);if (tmpNode.right != null) que.offer(tmpNode.right);len--;}resList.add(itemList);}}

但是迭代法還需要進(jìn)行練習(xí)。