[LeetCode]--111. Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

这个算法的难点就是，要判断左边或右边是否为空，因为如果一边为空，它的深度肯定是小于另外一边，但是此时为空的算是没有深度了，所以最小深度要为另一边不为空的。大家看下我最开始写的算法，始终是超时，我真是百思不得其解。

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

后来看了一下别人的算法。

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

是不是还是看不出来，为嘛它的能通过，而我写的超时了。研究了一会儿之后，我发现如果我直接判断是否为空，就不会超时了。

贴上代码吧

public class Solution { 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; else if (root.right == null) return minDepth(root.left) + 1; else return Math.min(minDepth(root.left), minDepth(root.right)) + 1; } }