The minimum depth of a binary tree

Leetcode-cn.com/problems/mi…

Their thinking

The problem is almost the same as finding the maximum depth of a binary tree. Calculate the depth of left and right subtrees separately, take the minimum value of both plus the root node is the minimum depth of the binary tree.

It is worth noting that if the sample is [1,2] and the left subtree depth is 1 and the right subtree depth is 0, the minimum depth of the binary tree is 2, not 1. If the right subtree is empty, the subtree with depth of 0 cannot be counted, that is, it does not exist. So the answer should be the depth of the left subtree plus the root node which is 1 plus 1.

With that in mind, we’ll use conditional statements alone to filter the three cases.

1. The left subtree is empty and the right subtree is not empty. return 1 + minDepth(root.right);

2. The left subtree is not empty and the right subtree is empty. return 1 + minDepth(root.left);

3. Neither the left subtree nor the right subtree is empty. return Math.min(minDepth(root.left), minDepth(root.right)) + 1;

The following code

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; }} * * /
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        } 
        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);
        if(root.left ! =null && root.right == null) {
            return 1 + leftDepth;
        } else if (root.left == null&& root.right ! =null) {
            return 1 + rightDepth;
        } else {
            return Math.min(leftDepth, rightDepth) + 1; }}}Copy the code