binary-tree - 二叉树的最小深度

Question

我正在阅读二叉树。在练习编码问题时，我遇到了一些解决方案，要求找到二叉树的最小深度。现在，根据我的理解深度是从根到节点(如果是叶节点/二叉树，则为叶节点)没有边

二叉树{1,2}的最小深度是多少

根据我的解决方案，它应该是 1。

Answer 1

我测试过的解决方案

public int minDepth(TreeNode root) {
    if(root == null){
        return 0;
    }
    int ldepth = minDepth(root.left);
    int rdepth = minDepth(root.right);
    if(ldepth == 0){
        return 1+rdepth;
    }else if(rdepth == 0){
        return 1+ldepth;
    }

    return (1 + Math.min(rdepth, ldepth));
}

在这里，我们计算节点的l深度(最小左子树深度)和r深度(最小右子树深度)。然后，如果l深度为零但r深度不为零，则意味着当前节点不是叶节点，因此返回1 + r深度。如果 r深度 和 l深度 都为零，那么“if”条件仍然有效，因为我们为当前叶节点返回 1+0。

“else if”分支的逻辑类似。在“return”语句中，由于两个“if”条件均失败，我们返回 1(当前节点)+ 左右分支递归调用的最小值。