首页 > 代码库 > [leetcode]_Minimum Depth of Binary Tree

[leetcode]_Minimum Depth of Binary Tree

2024-07-04 14:51:57   225人阅读

第五道树题，10分钟之内一遍AC。做树题越来越有feel~

题目：求一棵树从root结点到叶子结点的最短路径。

思路：仍然是递归。如果一个结点的左右子树任意一边为Null，该子树的minDepth应为非null子树的高度+1；如果一个结点的左右子树两边都非Null，则该子树的minDepth应为两个子树的较小值

代码：

public int minDepth(TreeNode root) {
        if(root == null) return 0;
        
        if(root.left == null && root.right == null) return 1;
        else if(root.left == null || root.right == null) 
            //如果该结点的left或者right为null,则该结点的depth应该为非null边子树高度 + 1
            return minDepth(root.left) + minDepth(root.right) + 1;
        else 
            //如果该结点的left和right都不等于null ,则该结点的depth应该为两边子树高度的较小值 + 1
            return Math.min(minDepth(root.left) , minDepth(root.right)) + 1;
    }

 if语句的前两种情况本可以合并书写，考虑到合并起来理解性太差了，就这样了。第二个return 中，由于 肯定有一个minDepth的返回值是0，所以我就直接取它们的和值了，不分两种情况来写。


联系
我们