解题思路

递归

最直接的思路就是递归。
我们用深度优先搜索来解决这个问题。

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

复杂度分析

• 时间复杂度：我们访问每个节点一次，时间复杂度为 O(N) ，其中 N是节点个数。
• 空间复杂度：最坏情况下，整棵树是非平衡的，例如每个节点都只有一个孩子，递归会调用 N（树的高度）次，因此栈的空间开销是 O(N) 。但在最好情况下，树是完全平衡的，高度只有 log(N)，因此在这种情况下空间复杂度只有 O(log(N)) 。

  深度优先搜索迭代

  我们可以利用栈将上述解法中的递归变成迭代。
  想法是对于每个节点，按照深度优先搜索的策略访问，同时在访问到叶子节点时更新最小深度。
  我们从一个包含根节点的栈开始，当前深度为 1 。
  然后开始迭代：弹出当前栈顶元素，将它的孩子节点压入栈中。当遇到叶子节点时更新最小深度。

public int minDepth(TreeNode root) {
        Stack<Pair<TreeNode,Integer>> stack = new Stack<>();
        if(root==null)
            return 0;
        else
            stack.add(new Pair<>(root,1));
        int min_depth = Integer.MAX_VALUE;
        while (!stack.isEmpty())
        {
            Pair<TreeNode,Integer> current = stack.pop();
            root = current.getKey();
            int current_depth = current.getValue();
            if(root.left==null&&root.right==null)
                min_depth=Math.min(min_depth,current_depth);
            if(root.left!=null)
                stack.add(new Pair<>(root.left,current_depth+1));
            if(root.right!=null)
                stack.add(new Pair<>(root.right,current_depth+1));
        }
        return min_depth;
    }