題目：

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

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

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

示例:

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

3/ \9 20/ \15 7

返回它的最小深度 ?2.

答案：

public class MinimumDepthOfBinaryTree {public static void main(String[] args) {TreeNode root = new TreeNode();root.val = 3;TreeNode left1 = new TreeNode();left1.val = 9;TreeNode righ1 = new TreeNode();righ1.val = 20;TreeNode left2 = new TreeNode();left2.val = 15;TreeNode right2 = new TreeNode();right2.val = 7;root.left = left1;root.right = righ1;righ1.left = left2;righ1.right = right2;System.out.println(minDepth(root)); // 結(jié)果 2System.out.println(minDepth1(root)); // 結(jié)果 2}private static int minDepth(TreeNode root) {if (root == null) {return 0; // 第一種情況}if (root.left == null && root.right == null) {return 1; // 第二種情況 左子和右子都為空，即為葉子節(jié)點}if (root.left != null && root.right != null) {int l = minDepth(root.left);int r = minDepth(root.right);return (l < r ? l : r) + 1; // 第三種情況 取左子和右子遍歷后的最小深度}if (root.left != null) {return minDepth(root.left) + 1; // 第四種情況 左子不為空，繼續(xù)遍歷左子} else {return minDepth(root.right) + 1; // 第五種情況 或者右子不為空，繼續(xù)遍歷右子}}// 另一種解法private static int minDepth1(TreeNode root) {if (root == null) {return 0; // 第一種情況}int l = minDepth(root.left);int r = minDepth(root.right);if (l == 0 || r == 0) {return l + r + 1; // 第二、四、五種情況}return l > r ? r + 1 : l + 1; // 第三種情況}}

?

?

?

?

?

?

總結(jié)

以上是生活随笔為你收集整理的【算法系列之一】二叉树最小深度的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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