首页 > itarticle > minimum depth of binary tree

minimum depth of binary tree

admin 11月 11, 2020 0

public int (TreeNode root) {
    if (root == null)
        return 0;
    return helper(root);
}

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

下面的代码是错误的

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

原因在于如果 1->null 这种，null不是叶子结点。那为啥求最大depth就不会出错？因为最大depth的操作是取最大值，如果子树是null，返回0，取最大值的操作就会把这个0跳过了。

public int maxDepth(TreeNode root) {
    if (root == null)
        return 0;
    int left = maxDepth(root.left);
    int right = maxDepth(root.right);
    return Math.max(left, right) + 1;
}