(20)Go递归求二叉树的最大深度和最小深度

求最大深度简单，主要是最小深度有个小陷进要注意

最大深度实现
func maxDepth(root *TreeNode) int {
	// 递归终止条件
	if root == nil {
		return 0
	}

	// 递归过程
	leftMaxDepth := maxDepth(root.Left)
	rightMaxDepth := maxDepth(root.Right)
	// 左右子树的最高深度+1
	return 1 + max(leftMaxDepth, rightMaxDepth)
}

func max(v1, v2 int) int {
	if v1 >= v2 {
		return v1
	}
	return v2
}

提交leetcode，通过

// 这里有个小陷阱,不能跟104反过来,因为叶子节点是没有左右子树的节点
// 如果按104的方案反过来,在[1,2]这种情况下,会返回1,而实际是2
// 所以要多一步判定,左子树为0,返回右子树深度+1,或者右子树为0,返回左子树深度+1
// 左右子树都为0,则返回1
func minDepth(root *TreeNode) int {
	// 递归终止条件
	if root == nil {
		return 0
	}

	// 递归过程
	leftMaxDepth := minDepth(root.Left)
	rightMaxDepth := minDepth(root.Right)

	// 左子树为0,返回右子树深度+1,
	// 右子树为0,返回左子树深度+1
	// 左右子树都为0,则返回1
	// 以上3种情况可以整合在一起，简化成以下写法
	if leftMaxDepth == 0 || rightMaxDepth == 0 {
		return leftMaxDepth + rightMaxDepth + 1
	}

	// 左右子树均不为空
	return 1 + min(leftMaxDepth, rightMaxDepth)
}

func min(v1, v2 int) int {
	if v1 < v2 {
		return v1
	}
	return v2
}

提交leetcode，通过