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.
给定二叉树,找出它的最小深度。最小深度是沿从根节点到最近叶节点的最短路径的节点数。
Java版本
public int run(TreeNode node) {
if(node == null)
return 0;
if(node.left == null && node.right == null)
return 1;
if(node.left == null)
run(node.right) + 1;
if(node.right == null)
run(node.left) + 1;
return Math.min(run(node.left), run(right));
}
算法解释:
整体采用递归算法,以根节点为起始点,分别算出左右孩子的最大深度,然后取出其最小值。
代码解释:
如果一个节点的左右孩子都为null,则此节点为叶子节点,所以其深度为1。
if(node.left == null && node.right == null)
return 1;
如果一个节点的左孩子为空,则计算其右孩子的深度,并返回最小值。
因为所有的节点都算一个深度值,所以要加1.
if(node.left == null)
run(node.right) + 1;
if(node.right == null)
run(node.left) + 1;