111.二叉树的最小深度

题目描述

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7],

  3
 / \
9  20
  /  \
 15   7

题解

DFS+递归

参考二叉树的最大深度的题目, 该题的难点在于, 若一个节点只有一个子树, 那么应该不考虑不存在的子树情况.

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

    if (root.left == null && root.right == null)
        return 1;

    int minDepth = Integer.MAX_VALUE;

    if (root.left != null)
        minDepth = Math.min(minDepth(root.left), minDepth);
    if (root.right != null)
        minDepth = Math.min(minDepth(root.right), minDepth);

    return minDepth + 1;

}

简化代码:

class Solution {
    public int minDepth(TreeNode root) {
        if(root == null) return 0;
        int m1 = minDepth(root.left);
        int m2 = minDepth(root.right);
        //1.如果左孩子和右孩子有为空的情况，直接返回m1+m2+1
        //2.如果都不为空，返回较小深度+1
        return root.left == null || root.right == null ? m1 + m2 + 1 : Math.min(m1,m2) + 1;
    }
}