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

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

代碼隨想錄 (programmercarl.com)

代碼隨想錄 (programmercarl.com)

111.二叉樹的最小深度

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

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

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

示例 1：

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

示例 2：

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

提示：

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

思路

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

這道題目要找一個深度最淺的葉子節(jié)點，即左右兒子皆為空，所以我們的遞歸結(jié)束條件即為left==right==null，而我們又需要找一個最淺的，所以當左右兩側(cè)節(jié)點均非空時，遞歸的返回值應(yīng)當是分別對兩者進行遞歸后的較小值加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é)點有一個兒子為空，則直接返回非空遞歸值加一即可。

層序遍歷總結(jié)

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

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);}}

但是迭代法還需要進行練習。