(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，通过